BZOJ4820: [Sdoi2017]硬币游戏

BZOJ4820: [Sdoi2017]硬币游戏

https://lydsy.com/JudgeOnline/problem.php?id=4820

分析:

• 好题，首先我们对这类问题一般可以大力高斯消元直接上。
• 由于是匹配多串问题，自然想到\(ac\)自动机，对每个节点进行消元。
• 但这样显然是过不去的，考虑只记录自动机上能直接获得答案的结点。
• 再记录一个结点表示失配的期望，然后求出向后匹配\(m\)个字符想匹配\(s_i\)却提前匹配到\(s_j\)的贡献就行了。
• 感觉说不明白，看看这篇博客吧
• https://www.cnblogs.com/zbh2047/p/9074750.html

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef double f2;
typedef long double f3;
typedef unsigned long long ull;
#define N 310
#define base 353448299
char w[N];
ull mi[N],h[N][N];
f2 mi2[N],P[N][N];
int n,m;
f2 a[N][N];
ull gh(int l,int r,int p) {
    return h[p][r]-h[p][l-1]*mi[r-l+1];
}
void Guass(int n) {
    int i,j,k;
    f2 del;
    for(i=1;i<=n;i++) {
        for(j=k=i;j<=n;j++) if(abs(a[j][i])>abs(a[k][i])) k=i;
        if(i!=k) for(j=i;j<=n+1;j++) swap(a[i][j],a[k][j]);
        del=a[i][i];
        for(j=i;j<=n+1;j++) a[i][j]/=del;
        for(j=1;j<=n;j++) if(j!=i) {
            del=a[j][i];
            for(k=i;k<=n+1;k++) {
                a[j][k]-=del*a[i][k];
            }
        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    int i,j,k;
    for(mi[0]=i=1;i<=m;i++) mi[i]=mi[i-1]*base;
    for(mi2[0]=i=1;i<=m;i++) mi2[i]=mi2[i-1]/2;
    for(i=1;i<=n;i++) {
        scanf("%s",w+1);
        for(j=1;j<=m;j++) {
            h[i][j]=h[i][j-1]*base+w[j];
        }
    }
    for(i=1;i<=n;i++) {
        for(j=1;j<=n;j++) {
            for(k=1;k<m;k++) {
                if(gh(1,k,i)==gh(m-k+1,m,j)) {
                    P[i][j]+=mi2[m-k];
                }
            }
        }
    }
    for(i=1;i<=n;i++) a[n+1][i]=1; a[n+1][n+2]=1;
    for(i=1;i<=n;i++) {
        a[i][n+1]=-mi2[m];
        a[i][i]++;
        for(j=1;j<=n;j++) {
            a[i][j]+=P[i][j];
        }
    }
    Guass(n+1);
    
    for(i=1;i<=n;i++) printf("%.10f\n",a[i][n+2]);
}

BZOJ4820: [Sdoi2017]硬币游戏

原文：https://www.cnblogs.com/suika/p/10165883.html