about 4 years ago

ac自动机多和dp联系在一起
http://hi.baidu.com/wwwaaannngggrs/item/b2b67acccea55f0dc710b211
f数组是邻接矩阵,自乘k次代表沿矩阵走k步,f[i][j]表示i到j的方案数
f[i][j] 是j转移到i的可能性
ans数组是结果。由于在数组里的下标都往后移了一位,ans[1][1]=f[0][0]=1【1、第0位匹配根节点的概率是100%。2、若为0的话会导致答案乘0失解】
f*ans的答案ans'[i][j] 代表n个点下一步转移到i点的可能性【注意矩阵乘法不满足交换律!!!!注意查错!被坑了好久……】
代码里有重载。
orz gty

/**************************************************************
    Problem: 2553
    User: LaVenDer
    Language: C++
    Result: Accepted
    Time:60 ms
    Memory:1376 kb
****************************************************************/

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
struct matrix
{
    long double a[80][80];
    int sx,sy;
    void dowith(int x,int y)
    {
        sx=x;sy=y;memset(a,0,sizeof(a));
    }
} ans,f;
matrix operator*(const matrix a,const matrix b)
{
    matrix temp;temp.dowith(a.sx,b.sy);
    for (int i=1;i<=temp.sx;i++)
      for (int j=1;j<=temp.sy;j++)
      {
        for (int k=1;k<=a.sy;k++)
          temp.a[i][j]+=a.a[i][k]*b.a[k][j];
      }
    return temp;
}
struct ac
{
    int ch[101][27];
    int fail[101],last[101],val[101];
    int sz,size;
    void dowith(int k)
    {
        sz=0;size=k;
        memset(fail,0,sizeof(fail));
        memset(last,0,sizeof(last));
        memset(val,0,sizeof(val));
        memset(ch,0,sizeof(ch));
    }
    void insert(char *st,int color)
    {
        int l=strlen(st),i;
        int pos=0;
        for (i=0;i<l;i++)
          st[i]=st[i]-'a'+1;
        for (i=0;i<l;i++)
          {
            if (!ch[pos][st[i]]) {ch[pos][st[i]]=++sz;}
            pos=ch[pos][st[i]];
          }
        val[pos]=color;
    }
    queue<int>q;
    void prepare()
    {
        int i,j,a,k,pos=0;
        for (i=1;i<=size;i++)
          if (ch[pos][i]) q.push(ch[pos][i]);
        while (!q.empty())
        {
            pos=q.front();q.pop();
            for (i=1;i<=size;i++)
            {
                if (!ch[pos][i]){ch[pos][i]=ch[fail[pos]][i];continue;}
                q.push(ch[pos][i]);
                j=fail[pos];
                while (j&&!ch[j][i]) j=fail[j];
                j=ch[j][i];
                fail[ch[pos][i]]=j;
            }
        }
    }
} t;
int n,len,alphabet;
char st[20];
matrix ksm(matrix f,int x)
{
    matrix temp;temp.dowith(f.sx,f.sy);
    for (int i=1;i<=f.sx;i++)
      temp.a[i][i]=1;
    for (int i=x;i>0;i>>=1)
    {
        if (i&1) temp=temp*f;
        f=f*f;
    }
    return temp;
}
int main()
{
    int i,j,k;
    scanf("%d%d%d",&n,&len,&alphabet);
    t.dowith(alphabet);
    for (i=1;i<=n;i++)
     {
        scanf("%s",st);
        t.insert(st,i);
     }
    t.prepare();
    f.dowith(t.sz+2,t.sz+2);
    long double temp=1.0/(long double)alphabet;
    for (i=0;i<=t.sz;i++)
    {
        for (j=1;j<=alphabet;j++)
          if (t.val[i]==0)
          {
            if (t.val[t.ch[i][j]])
            {
                f.a[1][i+1]+=temp;
                f.a[t.sz+2][i+1]+=temp;
            }
            else
              f.a[t.ch[i][j]+1][i+1]+=temp;
          }
    }
    f.a[t.sz+2][t.sz+2]=1;
    f=ksm(f,len); 
    ans.dowith(t.sz+2,1);
    ans.a[1][1]=1;
    ans=f*ans;
    printf("%.12lf\n",(double)ans.a[t.sz+2][1]);
}
← little of 斜率优化 【bzoj1010】【dp】【斜率优化】玩具装箱 →
 
comments powered by Disqus