babcs2035 https://blog.hatena.ne.jp/babcs2035/ きろく https://babcs2035.hateblo.jp/ 競技プログラミング AtCoder その他の問題 問題 解法 解答 問題 atcoder.jp 解法 dp(i, f) := 頂点 i を黒で塗れるかどうかが f のとき，頂点 i から到達できる頂点を塗り分ける通り数 と定義する．このとき， dp(i, f) = dp(v_1, true) * dp(v_2, true) * ... (f == false のとき) dp(i, f) = dp(v_1, false) * dp(v_2, false) * ... + dp(v_1, true) * dp(v_2, true) * ... (f == true のとき) (v は頂点 i から直接行ける頂点) と漸化式が立つ．状態数 O(N)… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbabcs2035.hateblo.jp%2Fentry%2F2019%2F01%2F07%2F173645" title="Educational DP Contest：P - Independent Set - きろく" 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/b/babcs2035/20190107/20190107173548.png Hatena Blog https://hatena.blog 2019-01-07 17:36:45 rich https://babcs2035.hateblo.jp/entry/2019/01/07/173645 1.0 100%