有n个球排成一列，每个球都有一个颜色，用A-Z的大写字母来表示，我们每次随机选出两个球ball1,ball2,使得后者染上前者的颜色，求期望操作多少次，才能使得所有球的颜色都一样？

Solution

挺不错的题！

其实n可以开到1e7

%%lrd真心好题解

思想：

1.26个太多，2个好做。

2.转化成2个？钦定哪一个最后成为最终颜色！这个是白色，剩下都是黑色。

发现问题：

问题1：不一定什么时候都能染成

概率：i/n

问题2：不能之前的f[i]剩下i个白球到全部是同样的颜色。必须都是白色并且都是黑色也不一定都是同样颜色的。

所以f[i]有i个白球，染成都是白色的期望步数

问题3：f[0]怎么定义？正无穷？

其实是条件概率，也就是，对于所有情况（S种），我们把所有最终变成char这种字母的情况拿出来（K种），统计每一个方案的步数，乘上概率(1/K)

再乘上：K/S，这里就是cnt[char]/n

所以其实，f[i]有一个条件，只统计能到达想要的全白状态下的期望步数

所以转移只用考虑“占比”（也就是占x/K），显然(i+1)的概率高，(i-1)的概率低，所以占比就是i+1:i-1

其实本质是条件概率再套条件概率

然后转移方程就列出来了，变成kx+b的形式

至于每次的恒定的g[i]，就理解为动一下。动到哪里不关心

#include<bits/stdc++.h>

#define il inline

#define reg register int

#define numb (ch^'0')

using namespace std;

typedef long long ll;

il void rd(int &x){

    char ch;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

const int N=+;

double g[N],f[N],k[N],b[N];

int cnt[];

int n;

char s[N];

int main(){

    scanf("%s",s+);

    n=strlen(s+);

    for(reg i=;i<=n;++i) ++cnt[s[i]-'A'];

    for(reg i=;i<=n;++i) g[i]=(double)n*(n-)/(i*(n-i))/2.0;

    for(reg i=n-;i>=;--i){

        k[i]=(i-)/(*i-(i+)*k[i+]);

        b[i]=((i+)*b[i+]+(*i*g[i]))/(*i-(i+)*k[i+]);

    }

    f[]=b[];

//  cout<<f[1]<<endl;

    for(reg i=;i<=n;++i){

        f[i]=k[i]*f[i-]+b[i];

    //  cout<<f[i]<<endl;

    }

    double ans=;

    for(reg i=;i<;++i){

        ans+=(double)cnt[i]/n*f[cnt[i]];

        //cout<<cnt[i]<<" "<<f[cnt[i]]<<" "<<ans<<endl;

    }

    printf("%.1lf",ans);

    return ;

}

}

signed main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2019/3/11 22:53:25

*/