题解：P10329 [UESTCPC 2024] Add

· · 题解

  又是一道期望题，楼上各位已经给出了题目的答案了，对于给定的 n，要输出 \sum_{i=1}^ni^2=n(n+1)(2n+1)/6。下面对于推导过程从概率论上给出一个比较严谨的证明。

记号与初值条件

 记 f(i,j) 表示经过第 i 次操作后 a_j 的值，E(i,j) 是 f(i,j) 的期望值。显然，我们有初值条件：

E(0,j)=f(0,j)=j(1\leq j\leq n)\tag{1}

递推式准备

  题目要求的就是 E(n-1,1)。我们首先可以找出一个递推关系。
  考虑第 i(1\leq i\leq n-1) 次操作，这次操作是将现在 a_{n-i+1} 的值随机加到 a_1 到 a_{n-i} 身上，概率各为 1/(n-i)。由于现在 a_{n-i+1} 的值是 f(i-1,n-i+1)，所以对于任意的 j，a_j 有 \cfrac{1}{n-i} 的概率被加，也有 \cfrac{n-i-1}{n-i} 的概率不变。因此，我们有：

f(i,j)=\cfrac{1}{n-i}\left[f(i-1,j)+2f(i-1,n-i+1)\right]+\cfrac{n-i-1}{n-i}f(i-1,j)=f(i-1,j)+\cfrac{2f(i-1,n-i+1)}{n-i}\tag{2}

  根据期望的线性性，对式 (2) 两边同时取期望，得：

E(i,j)=E(i-1,j)+\cfrac{2E(i-1,n-i+1)}{n-i}\tag{3}

重要等式准备

  考察式 (3)，发现 E(i,j) 与 E(i-1,j) 之间的差 D_i=\cfrac{2E(i-1,n-i+1)}{n-i}和 j 是无关的。所以：

E(i,j)=D_i+D_{i-1}+\cdots+D_1+E(0,j)=S_i+j\tag{4}

  其中 S_i=\sum_{k=1}^iD_k 仅仅是 i 的函数。根据式 (4)，可以得到以下等式：

E(i,j)-j=E(i,1)-1=S_i\tag{5}

  从而得到重要等式：

E(i,j)=E(i,1)+j-1\tag{6}

最终推导

  这时，一切都好办了。在 (3) 式中，我们令 j=1 得：

E(i,1)=E(i-1,1)+\cfrac{2E(i-1,n-i+1)}{n-i}\tag{7}

  根据重要等式 (6)，我们有 E(i-1,n-i+1)=n-i+E(i-1,1)。代入式 (7)，得：

E(i,1)=E(i-1,1)+\cfrac{2}{n-i}[n-i+E(i-1,1)]=2+\cfrac{n-i+2}{n-i}E(i-1,1)\tag{8}

  式 (8) 的形式已经是一个数列了，可以利用高中的已知递推公式求出通项公式。
  记b_i=E(i,1)，则根据式 (1)我们有初值 b_0=E(0,1)=1,式 (8) 可重写为：

b_i=\cfrac{n-i+2}{n-i}b_{i-1}+2\tag{9}

  在式 (9) 两边同时乘 (n-i)(n-i+1) 得：

(n-i+1)(n-i)b_i=(n-i+2)(n-i+1)b_{i-1}+2(n-i)(n-i+1)\tag{10}

  利用换元技巧 c_i=(n-i+1)(n-i)b_i 可以将式 (10) 重写为：

c_i=c_{i-1}+2(n-i)(n-i+1)\tag{11}

  同时还有初值 c_0=(n+1)nb_0=(n+1)n。式 (11) 是高中数列典型的一类题。由于多项式是 i 的二次多项式，我们尝试待定系数：

c_i=C_1i^3+C_2i^2+C_3i+C_4\tag{12}

  其中 C_k(k=1,2,3,4) 是待定系数。将式 (12) 代入式 (11) ，整理可以得到：

(3C_1-2)i^2+(4n+2-3C_1+2C_2)i+C_1-C_2+C_3-2n^2-2n=0\tag{13}

  能解得 C_1=2/3,C_2=-2n,C_3=2n^2-2/3。至于 C_4，C_4=c_0=n^2+n。
  所以 c_i=2i^3/3-2ni^2+(2n^2-2/3)i+n^2+n。只需代入 i=n-1，即得所求 E(n-1,1)=b_{n-1}=c_{n-1}/2=n(n+1)(2n+1)/6。