ranwen's blog

随便写写

[BZOJ2554]Color 申必期望

传送门

Description

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

Input

一行一个字符串,表示球的颜色

Output

一行表示结果,精确到小数点后1位。

Sample Input

AAA

Sample Output

0.0

HINT

数据范围 对于10%的数据,n<=20 对于40%的数据,n<=200 对于50%的数据,n<=1000 对于100% 的数据,n <= 10000

Source

Ctsc模拟赛By 洁妹

题解

首先我们可以发现,这道题其实与字母本身以及具体位置无关,只和各字母的个数有关。

为了方便,下文我将“将所有字母的颜色染成aa”简称为“aa全部覆盖”。

对于一种颜色aa,若我们求出颜色aa能全部覆盖的概率以及期望步数,我们便可以求出答案。

具体的,答案为E(a)×P(a)\sum E'(a)\times P'(a)

显而易见,若aabb的个数相同,则E(a)=E(b)E'(a)=E'(b)P(a)=P(b)P'(a)=P'(b)

由此结论,我们可以定义E(x)E(x)表示当字母个数为xx时全部覆盖的期望步数。

同理,定义P(x)P(x)表示当字母个数为xx时全部覆盖的概率。

现在我们针对某一个字母全部覆盖进行讨论,对于别的不同的字母是等价的。

我们设这个字母是aa,其余所有字母为bb

我们先计算P(x)P(x)

显而易见,P(n)=1,P(0)=0P(n)=1,P(0)=0

对于一个字符串有xxaa的状态SxS_x,可以在下一步直接转移到状态Sx1,Sx+1 S_{x-1},S_{x+1}\ 。对于所有的选法,可以算出有i×(ni)i\times(n-i)种可以转移到Sx1S_{x-1},有i×(ni)i\times(n-i)种转移到Sx+1S_{x+1},明显这两种转移概率相等。

所以有P(x)=P(x1)+P(x+1)2P(x)=\frac{P(x-1)+P(x+1)}{2},即P(x)P(x1)=P(x1)P(x2)P(x)-P(x-1)=P(x-1)-P(x-2)。所以数列PP等差。

易得P(x)=xnP(x)=\frac{x}{n}

至此,我们求出了P(x)P(x),之后我们计算E(x)E(x)

由上面所得结论,可以发现每次操作后xx变化的选择有2x(nx)2x(n-x),可以算出每次操作xx变化的概率为2x(nx)T\frac{2x(n-x)}{T},所以操作使xx变化的期望轮数为T2x(nx)\frac{T}{2x(n-x)}

值得注意的是,由于我们算得期望E(x)E(x)表示有xx个字母完全覆盖时的期望步数,而P(x1)P(x-1)P(x+1)P(x+1)不等,所以E(x1)E(x-1)E(x+1)E(x+1)E(x)E(x)带来的贡献的权重也不等,而带来的贡献的权重比就等于它们的完全覆盖的概率比。

因此,我们可以得出 E(x)=P(i1)×E(i1)+P(i+1)×E(i+1)P(x1)+P(x+1)+T2x(nx)=(x1)E(x1)+(x+1)E(x+1)2x+n(n1)2x(nx)E(x)=\frac{P(i-1)\times E(i-1)+P(i+1)\times E(i+1)}{P(x-1)+P(x+1)}+\frac{T}{2x(n-x)}=\frac{(x-1)E(x-1)+(x+1)E(x+1)}{2x}+\frac{n(n-1)}{2x(n-x)} 值得注意的是,我们求答案时求的是E(Cnti)×in\sum \frac{E(Cnt_i)\times i}{n}

我们不妨设f(x)=E(x)×xnf(x)=\frac{E(x)\times x}{n}

则上式可化为 f(x)×nx=f(x1)×n+f(x+1)×n2x+n(n1)2x(nx)\frac{f(x)\times n}{x}=\frac{f(x-1)\times n+f(x+1)\times n}{2x}+\frac{n(n-1)}{2x(n-x)}

2f(x)=f(x1)+f(x+1)+n1nx2f(x)=f(x-1)+f(x+1)+\frac{n-1}{n-x} f(x+1)=2f(x)f(x1)n1nxf(x+1)=2f(x)-f(x-1)-\frac{n-1}{n-x} 容易得到E(n)=0E(n)=0,又因为S0S_0永远无法完全覆盖,所以对期望不够成贡献(但是仍然有一定概率被转移到),所以我们令E(0)=0E(0)=0

所以可以得到f(n)=0,f(0)=0f(n)=0,f(0)=0

那么如何推出剩余的f(x)f(x)

(下面的结论我是先找规律后证明的,过程较乱)

我们先将x=n1x=n-1带入上式,得到 f(n)=2f(n1)f(n2)(n1)=0f(n)=2f(n-1)-f(n-2)-(n-1)=0

我们假设有 (nx+1)f(x)(nx)f(x1)(nx)(n1)=0(n-x+1)f(x)-(n-x)f(x-1)-(n-x)(n-1)=0

那么我们将f(x)=2f(x1)f(x2)n1nx+1f(x)=2f(x-1)-f(x-2)-\frac{n-1}{n-x+1}带入,得到 2(nx+1)f(x1)(nx+1)f(x2)(n1)(nx)f(x1)(nx)(n1)=(nx+2)f(x1)(nx1)f(x2)(nx+1)(n1)=02(n-x+1)f(x-1)-(n-x+1)f(x-2)-(n-1)-(n-x)f(x-1)-(n-x)(n-1) =(n-x+2)f(x-1)-(n-x-1)f(x-2)-(n-x+1)(n-1)=0

X=x1X=x-1,则可以得出

(nX+1)f(X)(nX)f(X1)(nX)(n1)=0(n-X+1)f(X)-(n-X)f(X-1)-(n-X)(n-1)=0 所以,上式成立。

所以,当X=1X=1时,可以得到 nf(1)(n1)f(0)(n1)(n1)=0nf(1)-(n-1)f(0)-(n-1)(n-1)=0

f(1)=(n1)2nf(1)=\frac{(n-1)^2}{n}

至此,我们得到了f(0)f(0)f(1)f(1)

我们只需要递推计算f(x)f(x)即可。

答案为f(Cnti)\sum f(Cnt_i)

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;
template<typename __T>
inline void read(__T &x)
{
    x=0;
    int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')    f=-1;c=getchar();}
    while(isdigit(c))    {x=x*10+c-'0';c=getchar();}
    x*=f;
}
char str[10005];
int cnt[66];
double dp[10005];
int n;
int main()
{
    scanf("%s",str);
    n=strlen(str);
    for(int i=0;i<n;i++)
        cnt[str[i]-'A']++;
    dp[1]=(n-1.0)*(n-1.0)/n;
    for(int i=1;i<n-1;i++)
        dp[i+1]=2*dp[i]-dp[i-1]-(n-1.0)/(n-i);
    double ans=0;
    for(int i=0;i<26;i++)
        ans+=dp[cnt[i]];
    printf("%.1lf\\n",ans);
    return 0;
}

参考

liu-runda

CQZhangyu

miskcoo

rising_shit

日期: 2018-04-11

标签: OI