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)