♥沙耶花の備忘録♥

F - Minflip Summation 行列累乗解法～京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）～

↓これ

最終的に文字が同じ連続区間の個数を $x$ とすると, $x=1$ の時は答えが $0$ , $x=2$ の時は答えが $1$ , $x=3$ の時は答えが $1$ , ...となりまふ. さらに, 区間の個数は直前の文字と異なるような文字の位置を $y$ 個とすると $y+1$ 個となりまふ.

$y$ が偶数の状態から奇数の状態になると必要な操作回数が $1$ 増えると言えることから, 文字列 $S$ の操作回数の期待値は次のような $dp$ をすると求められまふ.

$dp[i][j][k]$ ： $i$ 文字目まで考えた時点で $y$ の偶奇が $j$ で最後の文字が $k$ となる確率

尚, 期待値を表す変数は適当に外部に持っておいて $j$ が $0$ から $1$ になる瞬間にその時点の $dp$ 配列が表す確率を足すものとしまふ.

勿論これは $O(|S|K)$ かかってしまいまふが, これは行列累乗で高速化出来まふ. 具体的には, 各 $j,k$ に対して $dp[0][j][k]$ の値を $1$ にした状態で $S$ に対して上の $dp$ をすることで遷移の確率と期待値への寄与を求め, 得られた遷移と期待値への寄与を表す行列を $K$ 乗しまふ. ここで, 一文字目のために最後の文字が $0$ でも $1$ でもない状態みたいなのも用意すると面倒でない気がしまふ.

こうして求まるのは期待値なので, 最後に $2 ^{ (?の個数)}$ を掛けることで答えになりまふ.