codevs 5966 [SDOI2017]硬币游戏

输入描述 Input Description

输入输出数据精度为1e-10

[题解] 

#include<cstdio>
using namespace std;
const int N=1e3+5;
char s[N][N];
long double ec[N],f[N][N];
int va[N],vb[N];
int n,m;
void MakeMatrix(){
    ec[m]=1;
    for(int i=m-1;i;i--) ec[i]=ec[i+1]*0.5;
    for(int i=1;i<=n;i++){
        va[1]=0;
        for(int k=2,p=0;k<=m;k++){
            while(p&&s[i][k]!=s[i][p+1]) p=va[p];
            if(s[i][k]==s[i][p+1]) p++;
            va[k]=p;
        }
        for(int j=1;j<=n;j++){
            vb[0]=0;
            for(int k=1,p=0;k<=m;k++){
                while(p&&s[j][k]!=s[i][p+1]) p=va[p];
                if(s[j][k]==s[i][p+1]) p++;
                vb[k]=p;
            }
            for(int now=vb[m];now;now=va[now]) f[i][j]+=ec[now];
        }
        f[i][n+1]=1;
    }
}
void Guass(){
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n+1;j++) f[i][j]/=f[i][i];
        f[i][i]=1;
        for(int j=i+1;j<=n;j++){
            for(int k=i+1;k<=n+1;k++){
                f[j][k]-=f[i][k]*f[j][i];
            }
        }
    }
    for(int i=n;i;i--){
        for(int j=i+1;j<=n;j++){
            f[i][n+1]-=f[i][j]*f[j][n+1];
        }
    }
    long double sum=0,ans=0;
    for(int i=1;i<=n;i++) sum+=f[i][n+1];
    for(int i=1;i<=n;i++){
        ans=f[i][n+1];ans/=sum;
        printf("%.10f
",(double)ans);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
    MakeMatrix();
    Guass();
    return 0;
}