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）