SDOI2017硬币游戏

\(n,m300\)

很容易想到建出AC自动机后暴力高斯消元的\(O(^3m^3)40\)分做法

SOL：

这题和CSTC2006歌唱王国很像

定义:
\(a_{i,j,k}\)表示\(A_i[1,k]\)是否等于\(A_j[m-k+1,m]\)

\(f_{i,j}\)表示\(A_i\)出现时长度为\(j\)的概率，其生成函数为\(F_i(X)\)

\(g_i\)表示长度为\(i\)的序列未出现任何串的概率，其生成函数为\(G(x)\)

\[G(x)+\sum F_i(x)=1+G(x)*x\]

对于任意一个串\(i\)

\[G(x)*\frac 1{2^m}x^m=\sum_{j=1}^n\sum_{k=1}^ma_{i,j,k}*F_j(x)*\frac 1{2^{m-k}}x^{m-k}\]

将\(x=1\)代入二试：

\[G(1)=\sum^n_{j=1}\sum^m_{k=1}a_{i,j,k}*F_j(1)*2^k\]

需解出\(G(1),F_i(1)\)，加上\(\sum F_i(1)=1\)，一共\(n+1\)个式子，高斯消元即可

时间复杂度\(O(n^3)\)

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f==1?x:-x;
}
#define ll long long
const int N=304,mod=1e9+7;
const double eps=1e-10;
int n,m,h[N][N],b[N];
char s[N];
double a[N][N],db[N];
inline int hsh(int x,int l,int r){
    return (h[x][r]-(ll)h[x][l-1]*b[r-l+1]%mod+mod)%mod;
}
inline void gauss(int n){
    for(int i=1,id;i<=n;i++){
        id=i;
        for(int j=i+1;j<=n;j++)
            if(fabs(a[j][i])>fabs(a[id][i]))id=i;
        if(id!=i)swap(a[id],a[i]);
        for(int j=i+1;j<=n;j++){
            double tmp=a[j][i]/a[i][i];
            for(int k=i;k<=n+1;k++){
                a[j][k]-=a[i][k]*tmp;
            }
        }
    }
    for(int i=n;i;i--){
        for(int j=i+1;j<=n;j++)
            a[i][n+1]-=a[i][j]*a[j][n+1];
        a[i][n+1]/=a[i][i];
    }
}
int main(){
    n=read();m=read();
    b[0]=db[0]=1;
    for(int i=1;i<=m;i++){
        b[i]=(b[i-1]<<1)%mod;
        db[i]=db[i-1]*2;
    }
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=m;j++)
            h[i][j]=((h[i][j-1]<<1)+(s[j]=='H'))%mod;
    } 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            for(int k=1;k<=m;k++)
                if(hsh(i,1,k)==hsh(j,m-k+1,m))a[i][j]+=db[k];
        a[i][n+1]=-1;
    }
    for(int i=1;i<=n;i++)
        a[n+1][i]=a[n+1][n+2]=1;
    gauss(n+1);
    for(int i=1;i<=n;i++)
        printf("%.8lf\n",a[i][n+2]); 
    return (0-0);
}

SDOI2017硬币游戏

原文：https://www.cnblogs.com/aurora2004/p/12516678.html