BZOJ 1444 有趣的游戏(AC自动机+矩阵快速幂)

时间：2022-12-20 20:43:08

真的是很有趣的游戏。。。

对每个单词构建好AC自动机后，由于单词都是相同长度的且不同，所以不会出现互相为子串的形式。

那么我们对AC自动机上的节点构建转移矩阵。对于每个单词末尾的节点。该节点的出边仅仅与自己相连且概率为1.

表示如果已经出现了该单词游戏就结束了。答案是收敛的，我们对这个矩阵迭代个2^50次应该就可以求出近似的答案了。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi 3.1415926535

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

inline int Scan() {

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

struct Matrix{double matrix[N][N];}sa;

int trie[N][], top, fail[N], m, pos[N];

char s[N];

double P[N];

void init(){top=; mem(trie[],);}

void ins(char *s, int i){

    int rt, nxt;

    for (rt=; *s; rt=nxt, ++s){

        nxt=trie[rt][*s-'A'];

        if (!nxt) mem(trie[top],), trie[rt][*s-'A']=nxt=top++;

    }

    ++trie[rt][]; pos[i]=rt;

}

void makefail(){

    int u, v, bg, ed;

    static int q[N];

    fail[]=bg=ed=;

    FO(i,,m) if ((v=trie[][i])) fail[q[ed++]=v]=;

    while (bg<ed){

        u=q[bg++];

        FO(i,,m) {

            if ((v=trie[u][i])) fail[q[ed++]=v]=trie[fail[u]][i];

            else trie[u][i]=trie[fail[u]][i];

        }

    }

}

Matrix Mul(Matrix a, Matrix b) //矩阵乘法(%MOD)

{

    Matrix c;

    FO(i,,top) FO(j,,top) {

          c.matrix[i][j]=;

          FO(l,,top) c.matrix[i][j]+=a.matrix[i][l]*b.matrix[l][j];

    }

    return c;

}

int main ()

{

    int n, l, nxt;

    double x, y;

    scanf("%d%d%d",&n,&l,&m); init();

    FO(i,,m) scanf("%lf%lf",&x,&y), P[i]=x/y;

    FO(i,,n) scanf("%s",s), ins(s,i);

    makefail();

    FO(i,,top) {

        if (trie[i][]) {sa.matrix[i][i]=; continue;}

        FO(j,,m) nxt=trie[i][j], sa.matrix[i][nxt]+=P[j];

    }

    FOR(i,,) sa=Mul(sa,sa);

    FO(i,,n) printf("%.2f\n",sa.matrix[][pos[i]]);

    return ;

}

相关文章