ProjectEuler 430 - Range flips

problem 在此

根据 \(E(\sum X_i) = \sum E(X_i)\) 可以知道答案就是每个格子为白色格子的期望和。

对于第 \(1 \leq i \leq n\) 个格子，我们知道某次被翻转的几率是 \[p = \frac{2 i (n + 1 - i) - 1}{n^2}\]

令 \(f_k\) 表示 \(k\) 次翻转后仍然是白色的概率，可以得到 \[f_0 = 0, f_{k+1} = (1 - p) f_k + p (1- f_k)\] 可以化出 \[f_{k+1}- \frac{1}{2} = (1 - 2p) (f_k - \frac{1}{2})\] 于是有 \[f_k = \frac{1}{2}(1 + (1 - 2p)^k)\]

如果暴力做的复杂度是 \(O(10^{10} \log 4000)\) 。然后一个很小的优化是如果 \(1 - 2p \leq 0.99\) ，那么 \((1 - 2p)^k \leq 10^{-18}\) ，直接忽略不计了……

然后要跑 3min 才跑得出来。

如果有更好的做法求告诉我 >__<

（版面不够了于是只好用 display equation 来充版面么 LOL）