未証明要素を多分に含む怪しい解法で通してしまった
問題
解法
ちょうど $n$ 回の操作で終了する確率を $f _ n$ とする。$f _ n$ を直接計算するのは難しいので、終了条件を無視して $n$ 回の操作を行った後に終了条件を満たしている確率 $g _ n$ を考える。また、終了条件を満たしている状態から終了条件を無視して $n$ 回の操作を行った後に再び終了条件を満たしている確率 $h _ n$ を考える。
このとき、$f,g,h$ の母関数 $F,G,H$ について $FH = G$ が成り立つ。
$H = 1$ (この $H$ は $h$ の母関数ではなく盤面の行数である) の場合を考える。$c _ 1$ 個の 1 がある状態から (終了条件を無視して) $n$ 回の操作を行うことで $c _ 2$ 個の 1 がある状態になる確率は、以下で定める行列 $T = (t _ {i, j}) _ {0\leq i\leq W,\ 0\leq j\leq W}$ に対して ${T ^ n} _ {c _ 2, c _ 1}$ と表せる。
$$t _ {i, j} = \begin{cases} j / W & \text{if } i = j - 1 \\ 1 - j / W & \text{if } i = j + 1 \\ 0 & \text{otherwise} \end{cases}$$
$H$ が一般の場合に話を戻すと、上記考察より $i$ 行目に操作した回数 $t _ i$ を固定して数えることで、$g _ n$ は次で表せる。なお、初期盤面で $i$ 行目に存在する 1 の数を $B _ i$ とした。
$$ g _ n = \dfrac{n!}{H ^ n} \sum _ {t _ 1 + \cdots + t _ H = n} \prod _ {i = 1} ^ H \dfrac{1}{t _ i !} {T ^ {t _ i}} _ {A _ i, B _ i}. $$
さて、Cayley–Hamilton の定理より、$T$ の特性多項式を $p(x) \coloneqq \det(xI - T) = \sum _ {k = 0} ^ {W + 1} p _ k x ^ k$ とすれば、任意の整数 $n \gt W$ および $0\leq i, j\leq W + 1$ に対して次が成り立つ。
$${T ^ n} _ {i, j} = - \sum _ {k = 0} ^ W {T ^ {n - (W + 1 - k)}} _ {i, j} \cdot p _ k.$$
これは、$i, j$ を固定して数列 $a ^ {(i, j)}$ を ${a ^ {(i, j)}} _ n\coloneqq {T ^ n} _ {i, j}$ と定めれば、$a ^ {(i, j)}$ が $W + 2$ 項間の線形漸化式を持つことを表している。
また、$a ^ {(i, j)}$ の母関数は、ある $W$ 次以下の $q ^ {(i, j)}(x)$ が存在して $\dfrac{q ^ {(i, j)}}{\mathrm{rev}(p)}$ と表せる。$\mathrm{rev}(p)$ は $p$ の係数列を反転したものであり、$\mathrm{rev}(p)(x) = x ^ {W+1} p(1/x)$ である。$q ^ {(i, j)}$ の計算については、$q ^ {(i, j)}(x) = \left(\mathrm{rev}(p)(x) \cdot \sum _ {n = 0} ^ W {T ^ n} _ {i, j} x ^ n\right) \bmod x ^ {W + 1}$ に従って行えばよい。
以上より、$g _ n$ は次のように表せる。
$$g _ n = \dfrac{n!}{H ^ n} \sum _ {t _ 1 + \cdots + t _ H = n} \prod _ {i = 1} ^ H \dfrac{1}{t _ i !} \lbrack x ^ {t _ i}\rbrack \dfrac{q ^ {(A _ i, B _ i)}}{\mathrm{rev}(p)}. \tag{1}$$
$h _ n$ についても全く同様に考えることで次のように表せることが分かる。
$$h _ n = \dfrac{n!}{H ^ n} \sum _ {t _ 1 + \cdots + t _ H = n} \prod _ {i = 1} ^ H \dfrac{1}{t _ i !} \lbrack x ^ {t _ i}\rbrack \dfrac{q ^ {(A _ i, A _ i)}}{\mathrm{rev}(p)}. \tag{2}$$
適当な整数 $D$ を決めて、式 $(1),(2)$ に基づいて $G, H$ を $\mathrm{mod}\ x ^ D$ で計算すると、$F \bmod x ^ D$ を計算することができる。
さて、$f _ n$ が $K + 1\ (K\leq \lfloor D/2\rfloor)$ 項間線形漸化式を持つと予想する。この予想が正しければ、Berlekamp–Massey のアルゴリズムによって $F(x) = \dfrac{P(x)}{Q(x)}$ なる $P, Q$ を計算できるので、求める期待値を $F'(1) = \dfrac{P'(1) Q(1) - P(1) Q'(1)}{Q(1) ^ 2}$ として計算できる (本当？収束などの条件を確認していないのでかなり怪しい)。
いくらか実験すると $K = HW$ が成り立ちそうだったので、$D = 2HW + \varepsilon$ 程度で定めると AC が取れる。
提出
Submission #46252219 - AtCoder Regular Contest 136
感想
やってることが何もかも怪し過ぎて駄目だろという感じ。
これは余談なんだけど、持っている Berlekamp–Massey が Library Checker で通っていたのにバグっていて、大惨事になってしまった。Hack Case がどういうものかは分かったので取り敢えず issue を投げておいた。
