区域翻转

N个盘子放成一排，从左至右分别标记为1至N。每个盘子均为一面黑一面白，初始时所有的盘子都是白面朝上。

每轮从1到N中随机等概率选出两个数A和B（两数可以相同），并将A和B之间（包括A和B）的盘子翻转。

下例是N=8时一种可能的情形：其中第一轮$A=5, B = 2$，第二轮$A=4, B=6$。

记$E(N, M)$为M轮后白面向上的盘子数量的期望值，可以验证: $E(3,1)=10/9, E(3, 2)=5/3, E(10,4)\approx5.157, E(100,10)\approx51.893$。

求$E(10^{10}, 4000)$，结果保留小数点后2位小数。

本题难度:

解答

设第i个盘子在一轮中不被翻转的概率是$q_i$，被翻转的概率记为$p_i=1-q_i$，经过m次后白色向上的概率记作$x_i$。

显然当且仅当A和B都小于i或者都大于i时第i个盘子才不会被翻转，前者的概率是$(i-1)^2/n^2$，后者的概率是$(n-i)^2/n^2$，因此 $$p_i=1-\frac{(i-1)^2}{n^2}-\frac{(n-i)^2}{n^2}=\frac{2ni-2i^2+2i-1}{n^2}.$$ 经过m轮后其翻转次数服从二项分布，翻转次数为偶数时白色朝上，从而有 $$x_i=\frac{1}{2}\left((q_i+p_i)^m+(q_i-p_i)^m\right)=\frac{1}{2}\left(1+(1-2p_i)^m\right)=\frac{1}{2}\left(1+\frac{\left((n-2i)^2-4i+2\right)^m}{n^{2m}}\right).$$ 容易验证$x_i$的值是对称的，本题中n是偶数，所以只需考察i从1取到$n/2$的情形，因此有 $$E(n,m)=\sum_{i=1}^nx_i=\frac{n}{2}+\frac{1}{n^{2m}}\sum_{i=1}^{n/2}\left((n-2i)^2-4i+2\right)^m.$$ 本题只需要小数点后两位的精度，显然$(n-2i)^2-4i+2$应充分接近$n^2$，即i远小于n时$x_i$才足够大，因此从$i=1$开始遍历计算并汇总，设定一个阈值（以下设为$\epsilon=1/n$），当$(n-2i)^2-4i+2 < n^2\epsilon$时就停止循环，最终结果是$5000624921.38$。

注：因数据较大，为更好利用内建函数作快速幂，以下代码为Python 3。

n=10**10
m=4000
n2=n*n
epsilon=1/n

res=0
for i in range(1,n//2+1):
    a=pow(((n-2*i)*(n-2*i)-4*i+2)/n2,m)
    if a < epsilon:
        break
    res+=a

print(f"{res+n//2:.2f}")