東京海上日動プログラミングコンテスト2022 (AtCoder Beginner Contest 256) G - Black and White Stones (600)
制約から行列累乗を感じる
各辺に置く白石の数$ d毎に以下を考える
$ dp[l][i][j] で$ i番目の頂点を見て$ j=1なら現在の頂点が白、$ l=1なら最初の頂点が白の場合の数
初期値は以下のとおり
$ dp[0][1][0] = {}_{d-1}C_k
$ dp[0][1][1] = {}_{d-1}C_{k-1}
$ dp[1][1][0] = {}_{d-1}C_{k-1}
$ dp[1][1][1] = {}_{d-1}C_{k-2}
$ a_i = dp[x][i][0], b_i = dp[x][i][1] とすると、
$ \left(\begin{matrix} a_i \\ b_i \end{matrix}\right) = \left(\begin{matrix} {}_{d-1}C_k & {}_{d-1}C_{k-1} \\ {}_{d-1}C_{k-1} & {}_{d-1}C_{k-2} \end{matrix}\right) \left(\begin{matrix} a_{i-1} \\ b_{i-1} \end{matrix}\right)
なので最初の頂点が黒の場合と白の場合で分けて行列累乗を行うことで高速に求められる