题解 P3706 【[SDOI2017]硬币游戏】

· · 题解

题面

传送门

题解

这里介绍一下简单易懂的概率生成函数

概率生成函数

我们定义一个形式幂级数A(x)，称它为离散随机变量X的概率生成函数，当且仅当对于A(x)的每一项a_i，都有a_i=P(X=i)

容易发现以下几个性质

1.A(1)=\sum_{i=0}^\infty P(X=i)=1

2.A'(x)=\sum_{i=0}^\infty iP(X=i)x^{i-1}=E(X)

本题

我们先来考虑一个弱化版的问题，即n=1

这也太弱化了吧你随便抓个js都知道这是1啊……

不过我们现在考虑的是求此时扔硬币的期望次数是多少（实际上这个问题就是P4548 [CTSC2006]歌唱王国，你可以一并解决了）

这里我们假设它扔的不是个硬币而是个有m面的骰子，那么本题就是m=2的特殊情况了

我们定义一个字符串的前缀S[1,i]为这个字符串的border当且仅当S[1,i]=S[L-i+1,L]，其中L为串长

定义a_i，当且仅当S[1,i]是S的border时a_i为1，否则a_i为0

定义答案的概率生成函数为F(x)，即f_i表示掷了i次骰子游戏结束的概率，以及G(x)，g_i表示掷了i次骰子游戏仍未结束的概率

那么容易发现两个性质

1.G(x)+F(x)=1+xG(x)

也就是说g_i=g_{i+1}+f_{i+1}，即如果第i次未结束，那么第i+1次只有结束或未结束，+1是因为常数项

2.G(x)\left({1\over m}x\right)^L=\sum_{i=1}^La_iF(x)\left({1\over m}x\right)^{L-i}

即如果我们在一个未结束的串后面加上整个A肯定结束，然而还有可能没有加完整个串就已经结束了。通过分析可知，如果我们加了A的前i个字符之后结束，即有A[L-i+1,L]=A[1,i]，那么根据定义，A[1,i]是一个border，然后再把剩下的L-i个字符加进去就行了

对于1式，我们对两边求导，再把x=1代入，得

G'(x)+F'(x)=G(x)+xG'(x) F'(1)=G(1)

即我们所需要求的E(x)=F'(1)=G(1)

对于2式，我们把1代入，在两边同乘上m^L，得

G(1)=\sum_{i=1}^La_im^iF(1)

又因为F(1)=1，最终可以化作

E(x)=\sum_{i=1}^La_im^i

那么只要哈希就可以O(L)求出a_i了

n> 1

以上是n=1的情况，接下来我们就考虑串的个数大于1的情况

因为证明基本和上面差不多，下面我就不给证明直接放柿子了

定义P(A_i)=\prod_{i\in A_i}P_i

定义a_{i,j,k}，当且仅当A_i[1,k]=A_j[m-k+1,m]时值为1否则为0，可以用hash从而在O(n^3)的时间内解得

定义f_{i,j}表示首次出现的序列是A_i且随机序列长度为j的概率，F_i(x)为其生成函数，定义辅助序列g_i表示随机序列长度为i时仍未结束的概率，生成函数为G(x)

容易得到

G(x)+\sum_{i=1}^nF_i(x)=1+xG(x)

以及

G(x)P(A_i)x^m=\sum_{j=1}^n\sum_{k=1}^ma_{i,j,k}F_j(x)P(A_i[k+1,m])x^{L_i-k}

前一个柿子这里就不用管了，我们考虑后一个柿子，把x=1代入，可以得到

G(1)=\sum_{j=1}^n\sum_{k=1}^ma_{i,j,k}F_j(1)P({1\over A_i[1,k]})

对于每一个i都有这么一个方程，我们需要解出F_i(1)和G(1)，那么总共有n个方程和n+1个变量

等会儿好像还是不能解啊……

我们再转过头来看看……F_i(1)表示第i个人获胜的概率……那么似乎有

\sum_{i=1}^nF_i(1)=1

这样就有n+1个方程了，高斯削元就是了，时间复杂度O(n^3)

//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
const int N=305,P=1e9+7;const double eps=1e-10;
double mp[N][N],b[N];char s[N];int bin[N],h[N][N],n,m;
inline int Hash(R int i,R int l,R int r){return ((h[i][r]-1ll*h[i][l-1]*bin[r-l+1])%P+P)%P;}
void Gauss(int n){
    fp(i,1,n){
        if(mp[i][i]>-eps&&mp[i][i]<eps){
            fp(j,i+1,n)if(mp[j][i]<-eps||mp[j][i]>eps){
                fp(k,i,n+1)swap(mp[i][k],mp[j][k]);
                break;
            }
        }
        double t=1.0/mp[i][i];fp(j,i,n+1)mp[i][j]*=t;
        fp(j,i+1,n){
            t=mp[j][i];
            fp(k,i,n+1)mp[j][k]-=mp[i][k]*t;
        }
    }
    fd(i,n-1,1)fp(j,i+1,n)mp[i][n+1]-=mp[j][n+1]*mp[i][j];
}
int main(){
//  freopen("testdata.in","r",stdin);
    scanf("%d%d",&n,&m);
    bin[0]=b[0]=1;
    fp(i,1,m)bin[i]=(bin[i-1]<<1)%P,b[i]=b[i-1]*2;
    fp(i,1,n){
        scanf("%s",s+1);
        fp(j,1,m)h[i][j]=((h[i][j-1]<<1)+(s[j]=='H'))%P;
    }
    fp(i,1,n){
        fp(j,1,n)fp(k,1,m)(Hash(i,1,k)==Hash(j,m-k+1,m))?mp[i][j]+=b[k]:0;
        mp[i][n+1]=-1;
    }
    fp(i,1,n)mp[n+1][i]=1;mp[n+1][n+2]=1;
    Gauss(n+1);
    fp(i,1,n)printf("%.8lf\n",mp[i][n+2]);
    return 0;
}