AGC 034 F - RNG and XOR

確率分布の数列を $p$，答えの数列を $f$ とすると，

$\displaystyle{ \begin{aligned} f_0 &= 0 \\ f_i &= 1 + \sum_j p_jf_{i \oplus j} \qquad (i \neq 0) \end{aligned} }$

を解けば良い．

数列同士の bitwise XOR 畳み込み（$\ast$で表す）で書けるように $f_0$ の式の形を揃えたい．

$1 + \sum_j p_j f_j$ は状態 $0$ の平均再帰時間である．これは，マルコフ連鎖の性質から，$2 ^ N$ に等しい．

よって，数列 $g$ を $\displaystyle{ (1-2^ N,1,1,\ldots,1) }$ で定めると，

$\displaystyle{ f = g + p \ast f }$

となる．

数列 $e$ を $\displaystyle{ (1,0,\ldots,0) }$ で定めて，

$\displaystyle{ f=g \ast (e-p)^{-1} }$

を計算すればよい．

…と思って実装をすると，$0$ 除算発生！

よく考えると，$e-p$ をアダマール変換すると先頭の項が $0$ になってしまう（それ以外の項が $0$ になることはない）．

ところが，$f_0=0$ であることを既に知っているので $f$ をアダマール変換した結果の先頭の項はそれ以外の項の和の反数として求めることができる．めでたしめでたし．