Educational DP Contest DP まとめコンテスト - noko206/AtCoder GitHub Wiki

これは何？

★解説AC★

行列累乗。

$dp[n][i][j]:=$ 頂点 $i$ から頂点 $j$ へ行く長さ $n$ のパスの個数

と定義したとき、状態遷移は以下のようになる。

$dp[n][i][j]=\sum_k dp[n-1][i][k]*a[k][j]$

天才をすると、これが行列の積で書けることがわかって、 $A^K$ の各成分の合計が答えとなることがわかる。

コツとしては、↓らしい……。

制約を見る
- $N \le 50$ や、 $K$ が $10^9, 10^{18}$ みたいな場合は、サイズ $N^2$ の行列を $K$ 乗したら解けるかも
繰り返しに着目
- 同じ状態遷移を繰り返すものは行列累乗かも

↑ 行列の掛け算と累乗の計算をするライブラリを作った（パクった）。

桁DP。

$dp[i][j][smaller]:=$ $i$ 桁目まで決定したとき、 $D$ で割った余りが $j$ で、 $smaller$ が $1$ なら $K$ 未満、 $0$ なら $K$ と等しい値の個数。

と定義する。

桁DPの要は $smaller$ なので、そこの遷移に着目すると、

となる。

それ以外のコツとしては、↓ のような感じ。

★解説AC★

挿入DP。

$dp[i][j]:=$ $i$ 番目までで、最後が $j$ のときの場合の数

★解説AC★ ※遷移式が思いつかなかった……。

部分集合の部分集合は $O(3^N)$ 。

$dp[S]:=$ 集合 $S$ をいくつかのグループに分けたときの総得点の最大値。

集合 $S$ の部分集合 $T$ を $1$ つのグループとして、部分集合 $S/T$ と合体する遷移を考える
集合 $T$ は集合 $S$ の部分集合なので、 $S/T$ は $S-T$ で計算可能
部分集合をループするときは for (int T = S; ; T = (T - 1) & S) と書く
- 終了条件や continue 条件は適宜追加する

全方位木DP。

ライブラリを持っていたのでペタリ。あとは遷移式を頑張って立てる。

merge(a,b):=a*b%m（部分木同士の場合の数は独立して考えられるので掛け算で求まる）
add_root(a):=(a+1)%m（rootを含む部分木の全ての頂点が白の場合を考慮して+1）
- u->vに遷移するとき、頂点vが黒のときは sum_dp[u] 通り、頂点vが白のときは 1 通りであることから式を立てる
e():=1（add_rootで+1されて白黒両方の場合の数になるため）

get_vにrootが白の場合の数が含まれている点に注意して、 -1した値を答えとして出力する。