总结

概率的递推符合DP的递推思想，因此我们常利用DP解决概率问题

E - Random Swaps of Balls

地址

不难想到用dp[i]表示第i次操作后的期望位置，难点在递推式

先给出结论

$$ dp[i]=\frac{(n-1)\times (n-1)}{n\times n}\cdot dp[i-1]+\frac{1}{n}\cdot \frac{\sum_{i=1}^{n}}{n}\cdot 2-\frac{1}{n^2}\cdot dp[i-1] $$ $\frac{(n-1)\times (n-1)}{n\times n}$表示没有选中上一次位置的概率。递推式的第二项中，$\frac{1}{n}$表示选中上一次的概率，$\frac{\sum_{i=1}^{n}}{n}$表示选择交换的期望位置，2表示选择的先后顺序

$\frac{1}{n^2}\cdot dp[i-1]$是不会改变位置的概率，需要减去

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void SINGLE_TEST() 
{
    Z n;
    int k;
    cin>>n>>k;
    vector<Z> dp(k+1);
    dp[0]=1;
    for(int i=1;i<=k;i++){
        dp[i]=(n-1)*(n-1)/(n*n)*dp[i-1]+1/n*(n+1)*n/2/n*2-dp[i-1]/(n*n);
    }
    cout<<dp[k]<<"\n";
}