4820: [Sdoi2017]硬币游戏

链接

分析：

　　期望dp+高斯消元。

　　首先可以建出AC自动机，Xi表示经过节点i的期望次数，然后高斯消元，这样点的个数太多，复杂度太大。但是AC自动机上末尾节点只有n个，并且只有n个有用。所以考虑优化一下。

　　一个串内部的转移是没有必要的，考虑转移到结尾节点的转移。

　　当前的一个串S如果加入一个字符串T，变成ST，那么一定会结束，因为T这个字符串出现了。但是可能在T的某个前缀就出现了， 即存在一个字符串的后缀是T的前缀，那么统计出这样的转移，然后高斯消元。

　　加了eps后WA了？

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<iostream>

#include<cctype>

#include<set>

#include<vector>

#include<queue>

#include<map>

#define fi(s) freopen(s,"r",stdin);

#define fo(s) freopen(s,"w",stdout);

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

char s[N][N];

int p[N][N], n, m;

double mi[N], A[N][N];

void init(char *s,int *p) {

    for (int i = ; i <= m; ++i) {

        int j = p[i - ];

        while (j && s[j + ] != s[i]) j = p[j];

        if (s[j + ] == s[i]) j ++;

        p[i] = j;

    }

}

double Calc(char *a,char *b,int *p,bool f) {

    int j = ;

    for (int i = ; i <= m; ++i) {

        while (j && b[i] != a[j + ]) j = p[j];

        if (b[i] == a[j + ]) j ++;

    }

    if (f) j = p[j];

    double res = ;

    while (j) res += mi[m - j], j = p[j];

    return res;

}

void Gauss() {

    for (int k = ; k <= n; ++k) {

        int r = k;

        for (int i = k + ; i <= n; ++i) if (fabs(A[i][k]) > fabs(A[r][k])) r = i;

        if (r != k) for (int j = ; j <= n + ; ++j) swap(A[r][j], A[k][j]);

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

            if (fabs(A[i][k]) > ) {

                double t = A[i][k] / A[k][k];

                for (int j = ; j <= n + ; ++j) A[i][j] -= t * A[k][j];

            }

        }

    }

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

        for (int j = i + ; j <= n; ++j) A[i][n + ] -= A[i][j] * A[j][n + ];

        A[i][n + ] /= A[i][i];

    }

}

int main() {

    n = read(), m = read();

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

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

        init(s[i], p[i]);

    }

    mi[] = ;

    for (int i = ; i <= m; ++i) mi[i] = mi[i - ] * 0.5;

    for (int i = ; i <= n + ; ++i) A[][i] = ;

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

        A[i][] = -mi[m]; A[i][i] = 1.0;

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

            A[i][j] += Calc(s[i], s[j], p[i], i == j); // 计算字符串i转移到j的概率，即求i的前缀等于j的后缀

    }

    Gauss();

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

    return ;

}