简单的讲一讲。

我们可以钦定某一个魔法属性,使得这个魔法属性是最终的属性。

那么其贡献很显然就是该属性变为最终属性的概率$\times$该属性变为最终属性所需要的期望步数

将其依次求出。


概率。

很显然如果当前局面有 $i$ 个当前魔法属性,那么这一次操作有 $\frac{2i(n-i)}{n(n-1)}$ 的概率使得 $i$ 变化,其中 $\frac{i(n-i)}{n(n-1)}$ 的概率使得 $i$ 加 $1$ ,$\frac{i(n-i)}{n(n-1)}$ 的概率使得 $i$ 减 $1$ 。

设 $p_i$ 表示当前有 $i$ 个答案魔法属性时,钦定的魔法属性变为最终答案的概率。

可以得到 $p_i=\frac{p_{i-1}+p_{i+1}}{2}$ ,因为是等差数列,所以可以得到 $p_i=\frac{i}{n}$ 。


期望。

设 $f_i$ 表示当前有 $i$ 个答案魔法属性时,钦定的魔法属性变为最终答案的期望步数。

注意这是条件期望,也就是说转移的时候对于 $f_{i-1}$ 和 $f_{i+1}$ 我们不能给其分配一样的概率,毕竟两个状态到最终状态的概率不一样。

所以转移方程为:

$$f_{i}=\frac{n(n-1)}{2i(n-i)}+\frac{i-1}{2i}f_{i-1}+\frac{i+1}{2i}f_{i+1}$$

这样直接用线性高斯消元即可,复杂度 $O(n)$ 。


代码。

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
 
const int N=1e4+2;
 
double f[N],a[N],b[N],inv,num,ans;
int n,tot[27];
char s[N];
 
int main() {
    scanf("%s",s+1);
    for(n=1;s[n];++n) ++tot[s[n]-'A'];
    --n,a[1]=1,b[1]=0.5*n;
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)
        scanf("%lf",&inv);
    for(int i=2;i<n;++i) {
        inv=0.5/i,num=1.0/(1-(i-1)*inv*a[i-1]);
        a[i]=(i+1)*inv*num;
        b[i]=((i-1)*inv*b[i-1]+n*(n-1)*inv/(n-i))*num;
    }
    for(int i=n-1;i>=1;--i) f[i]=a[i]*f[i+1]+b[i];
    for(int i=0;i<26;++i) ans+=1.0*tot[i]/n*f[tot[i]];
    printf("%.1lf\n",ans);
    return 0;
}
最后修改:2019 年 08 月 24 日 04 : 04 PM