[BZOJ1444][JSOI2009]有趣的游戏(AC自动机,概率动态规划,矩阵快速幂)

发布于 2018-03-24  69 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1444][JSOI2009]有趣的游戏(AC自动机,概率动态规划,矩阵快速幂)

Description

BZOJ1444

Tag

AC自动机,矩阵快速幂

解决思路

把每一个人获胜的字符串构建出AC自动机。
设 F[i][j] 表示第 i 轮,当前在 AC 自动机的 j 号点的概率,那么按照对应概率向儿子分别转移。注意,当已经到达某一个任的字母序列尾时,此时标志某一个人胜利,那么就每一次只向自己转移。
转移多少次呢?很多很多次,只要精度小于两位即可。为了多次转移,可以矩阵快速幂优化,这样就不会有精度问题了。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define ld double
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=510;
const int maxAlpha=510;
const int maxTrie=510;
const int inf=2147483647;

class TrieData
{
public:
    int end,fail;
    int son[maxAlpha];
};

int n,l,m,nodecnt;
TrieData T[maxTrie];
ld Gl[maxAlpha];
char Input[maxN];
int Id[maxN],Queue[maxTrie];

class Matrix
{
public:
    ld M[maxTrie][maxTrie];
    Matrix(){mem(M,0);}
    Matrix(ld arr[maxTrie][maxTrie]){
        for (int i=0;i<maxTrie;i++)
            for (int j=0;j<maxTrie;j++)
                M[i][j]=arr[i][j];
    }
};

Matrix Ret;

void Insert(char *str,int id);
void GetFail();
void Mul1();
void Mul2();

int main()
{

    scanf("%d%d%d",&n,&l,&m);
    for (int i=1;i<=m;i++)
    {
        int p,q;scanf("%d%d",&p,&q);
        Gl[i-1]=(ld)p/(ld)q;//得到每一种字母的出现概率
    }

    for (int i=1;i<=n;i++)
    {
        scanf("%s",Input+1);
        Insert(Input,i);
    }
    GetFail();//构建AC自动机
    //构造初始矩阵
    for (int i=0;i<=nodecnt;i++)
    {
        if (T[i].end) Ret.M[i][i]=1;//当是单词末尾时,此时该人胜利,那么就只向自己转移
        else for (int j=0;j<m;j++) Ret.M[i][T[i].son[j]]+=Gl[j];//否则,向所有儿子依据概率转移
    }
    for(int i=100;i>=0;i--){//矩阵快速幂
        Mul2();
    }
    for (int i=1;i<=n;i++) printf("%.2lf\n",Ret.M[0][Id[i]]);
    return 0;
}

void Insert(char *str,int id)
{
    int now=0;
    for (int i=1;i<=l;i++)
    {
        if (T[now].son[str[i]-'A']==0) T[now].son[str[i]-'A']=++nodecnt;
        now=T[now].son[str[i]-'A'];
    }
    Id[id]=now;T[now].end=1;return;
}

void GetFail()
{
    int h=0,t=0;
    for (int i=0;i<m;i++) if (T[0].son[i]) Queue[++h]=T[0].son[i];
    while (h!=t)
    {
        int u=Queue[++t];
        for (int i=0;i<m;i++)
            if (T[u].son[i])
            {
                T[T[u].son[i]].fail=T[T[u].fail].son[i];
                Queue[++h]=T[u].son[i];
                T[T[u].son[i]].end|=T[T[T[u].fail].son[i]].end;
            }
            else T[u].son[i]=T[T[u].fail].son[i];
    }
    return;
}

ld Backup[maxTrie][maxTrie];

void Mul2()
{
    for (int i=0;i<=nodecnt;i++) for (int j=0;j<=nodecnt;j++) Backup[i][j]=Ret.M[i][j],Ret.M[i][j]=0;
    for (int i=0;i<=nodecnt;i++)
        for (int j=0;j<=nodecnt;j++)
            for (int k=0;k<=nodecnt;k++)
                Ret.M[i][j]=Ret.M[i][j]+Backup[i][k]*Backup[k][j];
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1444][JSOI2009]有趣的游戏(AC自动机,概率动态规划,矩阵快速幂)


HNCJ OIer