洛咕 P3706 [SDOI2017]硬币游戏

假设f[i]是第i个同学胜利的概率，也就是随机序列第一个匹配到s[i]的概率

假设前面有一个字符串\(S\)，（假设无限长但没有匹配），现在往后面要加上第i个串\(s[i]\)，这个的概率设为\(P_i\)。因为所有s[i]长度一样，所以每个\(P_i\)都相等。

　　　　S　　　　　s[i]　

现在在\(S\)后面加\(s[i]\)的时候，可能先匹配到了别的串

　　　　S　　　　　s[i]　

　　　　　　　s[j]　

假设\(S\)与\(s[j]\)的匹配长度为\(a\),\(s[i]\)与\(s[j]\)的匹配长度为\(b\)，因为\(S\)不确定，所以长度为\(a\)那一段匹配到的概率是\(2^{-a}\)

列出式子来，就是：

\(P=P_i=\sum_{j=1}^n\sum_{k=1}^{m}[s[j][m-k+1..m]==s[i][1..k]]2^{-k}\)

很玄学是吧我也觉得很玄学

所以可以把\(P\)看做是单位1，有n个方程，每个f[i]都是一个未知数，高斯消元即可，就能算出来f[i]之间的比例了，因为所有f[i]之和为1所以就求出答案了

#include<bits/stdc++.h>

#define il inline

#define vd void

#define mod 993244853

typedef long long ll;

il int gi(){

    int x=0,f=1;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

char S[310][310];

int n,m,Base[310];

int Hash[310][310],pre[310][310],suf[310][310];

double a[310][310],ans[310],p2[310];

int main(){

    n=gi(),m=gi();

    Base[0]=1;for(int i=1;i<=m;++i)Base[i]=Base[i-1]*19260817ll%mod;

    for(int i=1;i<=n;++i){

        scanf("%s",S[i]+1);

        for(int j=1;j<=m;++j)Hash[i][j]=(Hash[i][j-1]+1ll*S[i][j]*Base[j])%mod;

        for(int j=1;j<=m;++j)pre[i][j]=1ll*Hash[i][j]*Base[m-j]%mod;

        for(int j=1;j<=m;++j)suf[i][j]=(Hash[i][m]-Hash[i][m-j]+mod)%mod;

    }

    p2[0]=1;for(int i=1;i<=m;++i)p2[i]=p2[i-1]*0.5;

    for(int i=1;i<=n;++i){

        a[i][n+1]=1;

        for(int j=1;j<=n;++j)

            for(int k=1;k<=m;++k)

                if(pre[i][k]==suf[j][k])

                    a[i][j]+=p2[m-k];

    }

    for(int i=1;i<=n;++i){

        for(int j=i;j<=n;++j)if(fabs(a[j][i])>1e-5){std::swap(a[i],a[j]);break;}

        if(fabs(a[i][i])<1e-5)continue;

        for(int j=i+1;j<=n;++j){

            if(fabs(a[j][i])<1e-5)continue;

            double p=a[i][i]/a[j][i];

            for(int k=i;k<=n+1;++k)a[j][k]=a[j][k]*p-a[i][k];

        }

    }

    double sum=0;

    for(int i=n;i;--i){

        if(fabs(a[i][i])<1e-5)continue;

        for(int j=i+1;j<=n;++j)a[i][n+1]-=a[i][j]*ans[j];

        ans[i]=a[i][n+1]/a[i][i];sum+=ans[i];

    }

    for(int i=1;i<=n;++i)printf("%.10lf\n",ans[i]/sum);

    return 0;

}

巴特西

洛咕 P3706 [SDOI2017]硬币游戏

最新文章

热门文章