TheSwapsDivOne

作者：翁文涛 徐明宽

关键词：概率，期望，Dp，递推数列

题目简述

给定一个长度为$n$的序列$a$，有一个人会对这个序列进行$k$轮操作。每一轮，这个人会随机选择两个位置$i < j$，并交换$a_i,a_j$。操作完后，他会随机选择这个序列的一段连续区间$x \leq y$，记$sum = \sum_{i=x}^y a_i$，问$sum$的期望是多少。

数据范围

$n \leq 2209$ $k \leq 10^6$

算法一

令$prob_i$表示最终$i$这个位置是否被选中，$b_i$表示位置$i$最终的值，那么有： $$sum=\sum_{i=1}^n prob_i \times b_i \\ E[sum] = E\left[\sum_{i=1}^n prob_i \times b_i\right]\\ E[sum] = \sum_{i=1}^n E[prob_i \times b_i]\\ E[sum] = \sum_{i=1}^n E[prob_i]E[b_i]\\ $$ 那么问题就变成，对于每个位置$i$，求出$E[prob_i]$和$E[b_i]$，$E[prob_i]$非常好求，就等于 $\frac{i\times(n-i+1)}{\binom{n}{2}+n}$，现在关键就是求出$E[b_i]$。 令$f[i][j][k]$表示，第$i$个位置经过$k$轮被移到了第$j$个位置的概率。那么对于$i \not =j$，我们可以得到$f[i][j][k]$的转移式： $$f[i][j][k] = \frac{f[i][j][k-1] \times \binom{n-1}{2}+\sum_{x\not=j}f[i][x][k-1]}{\binom{n}{2}}$$ 其中，第一项表示第$k$轮交换没有选中位置$j$的概率，第二项表示之前是位置$i$移到位置$x$，然后第$k$轮选择了$x,j$来交换。 那么显然，$f[i][i][k]=1-\sum_{j \not = i} f[i][j][k]$。 直接这样做是会超时的，我们不妨观察$f[i][j][k]$的转移，可以发现，由于$f[i][i][0]=1$，$f[i][j][0]=0,i \not = j$，并且转移中并没有将$i,j$具体的值代入计算，因此，可以用数学归纳法简单的证明出，假如$k$固定，对于任意$i \not = j$，$x \not = y$，有$f[i][j][k] = f[x][y][k]$，且$f[i][i][k] = f[x][x][k]$。 那么我们可以稍微修改一下dp的状态。设$p[k]=f[i][j][k],i \not = j$，$g[k] = f[i][i][k]$，那么我们可以根据$f[i][j][k]$的转移，轻松写出$p[k]$和$g[k]$的转移： $$p[k] = \frac{p[k-1]\times \binom{n-1}{2}+g[k-1]+(n-2)\times p[k-1]}{\binom{n}{2}}\\ g[k]=1-(n-1)\times p[k]$$ 那么我们可以$O(k)$求出$p[k]$和$g[k]$。 最后，$E[b_i]=\sum_{j \not = i} a_j \times p[k] + a_i \times g[k]$。

算法二

注意到$\lim_{k \to \infty} g[k] = \frac{1}{n}$，记$x[k] = g[k] - \frac{1}{n}$，则由于$g[k]= \frac{n-2}{n} g[k-1] + \frac{1}{\binom{n}{2}}\left(1-g[k-1]\right)$，有 $$x[k] = \frac{n-3}{n-1} x[k-1] = \left(\frac{n-3}{n-1}\right)^k x[0] = \left(\frac{n-3}{n-1}\right)^k\frac{n-1}{n}$$ 所以直接一个pow就好啦~于是总时间复杂度就变成$O(n)$了（瓶颈为输入……）