题目链接

做的非常难受的一道，概率的题着实不好想。

我们设dp[i]为第i次选择后黑球第x个位置的概率，因此我们就可以对于黑球的位置分成两种情况讨论。

  • 上一次就在第x个位置，那么这一次只要让黑球的位置不发生改变即可，概率就是\frac{(n-1)^{2}}{n^{2}} + \frac{1}{n^{2}},第一部分表示的是只选择白球，第二部分表示只选择黑球。
  • 上一次不在第x个位置，也就是要让黑球和在$x$位置上的白球进行交换，由上一种情况我们可以得到$x$的可能位置(n-1)个位置的总概率之和是1 -(\frac{(n-1)^{2}}{n^{2}} + \frac{1}{n^{2}}) \rightarrow \frac{2*(n-1)}{n^{2}},呢么其中一个x的位置的概率就是\frac{\frac{2*(n-1)}{n^{2}}}{n-1}\rightarrow\frac{2}{n^{2}}

最终我们就可以得到递推方程：

dp[i] = dp[i-1] * (\frac{(n-1)^{2}+1}{n^{2}} ) + (1 - dp[i-1]) * (\frac{2}{n^{2}})

我们接着设 f[i]为第i次选择后黑球第x个位置的期望，因为i=0时，黑球的位置一定，所以f[0] = 1,并且我们由n显然可以得出总共可能的交换组合数\frac{(1+n) * n}{2}，接下来根据上求概率的式子我们就可以得出期望的递推方程：

\left\{\begin{array}{l} f[i] = 0  &      & {i =0}
\\ f[i] = f[i-1] * (\frac{(n-1)^{2}+1}{n^{2}} ) + ( \frac{(1+n) * n}{2}- f[i-1]) * (\frac{2}{n^{2}})&      & {i > 0}
\end{array}\right.