drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder1200点 ARC-F 数え上げ問題 トポロジカルソートの数え上げ グラフ・盤面・数列の個数の数え上げ グラフ 最小全域木 bitDP 順列の数え上げ 総和を求める 高速ゼータ変換 考察：順序を工夫して解く 順序の工夫：選択肢が狭い方から決めていく 挿入DP データ構造テク：前処理 DFS サイクル ARC-like 銅色diff 全域木を考える 個人的要復習 高度典型 解空間:O(N!)通りの選択肢 こういうの素早く解けるようになりたいね。 いわゆる「トポロジカルソート順の数え上げ」という高難易度でたまに見るパターンの問題。 問題へのリンク 問題概要 頂点 辺の無向グラフが与えられる。ここで、辺 が全域木を形成していることが保証されている。 各辺に の重みをつける 通りの方法のうち、 の辺たちが最小全域木をなすものが何通りあるか、109 + 7 で割った余りを求めよ。 制約 考えたこと： トポロジカルソート数え上げへの帰着 まずは最小全域木の特徴づけが MST をなす辺以外の各辺 に対して、その辺と MST とでサイクルが 1 つ形成されるが、その中で の重みが最大である で与えられること… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2019%2F05%2F13%2F011200" title="diverta 2019 F - Edge Ordering (銅色, 1200 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/d/drken1215/20190512/20190512113143.png Hatena Blog https://hatena.blog 2019-05-13 01:12:00 rich https://drken1215.hatenablog.com/entry/2019/05/13/011200 1.0 100%