POJ2778 - AC自动机+非递归的矩阵乘法

回想还是半个月前...跟着Matrix67的那文章做矩阵乘法....做到这题就卡住了...决心突破..这两周从Trie入门开始..到今天终于把这题给AC了...虽然这半个月做题量相比以前大大减少....但真正能初步掌握一种算法还是值得的...

首先这道题我是参考了几个解题报告的:

http://www.matrix67.com/blog/archives/276/

http://blog.csdn.net/dooder_daodao/article/details/6711186

如果需要具体思路请先看前面两篇..特别是后面一个题解很详细..并且代码很整洁...可以看出很多东西....

我就说下我做这题时出现的问题以及要注意的地方...

1、 ***A表示长度为4末位为A前三位任意但其不能是任意病毒的前缀..****代表长度为4每位都任意但其不能是任意病毒的前缀

2、Built_AC_Automation时word标记需要逆向的传递...

3、Built_AC_Automation时某个点没有哪个孩子不需要任何处理..而我开始是按POJ3691的方式处理的...

4、Built_Matrix时问题很多...这个矩阵的意义是各个前缀相互到达方案数...表示每个前缀添加一个字符能转化到另一个前缀的方案数..

5、Built_Matrix时...注意什么时候要对0点更新..也就是要找的点在其以及其当其不断向上Fail是都没有这个孩子...就要更新矩阵的0列...但如果这个过程中有某个点其孩子有但是其孩子是病毒点..那也不能更新矩阵的0列..应该不做任何操作..

6、Built_Matrix时...若在其或者其向上Fail的某个点的孩子找到了能更新的点...那在++后就不要继续向上Fail了...因为继续往上在找到的实际上还是最先找到的那个..会重复的加..

7、 矩阵乘法时不能用递归...递归会爆内存..所以只能将其拆分成二阶乘数的和..

8 、切记!!矩阵里每个单元要是long long的...因为10^5 * 10^5会爆int !!

好久没写这么长的代码了...特别是非模拟题..怀疑这是我非模拟题写的最长的..比网络流的还长...PS: 我构造矩阵时就先将没用的点给去了..也就是病毒点..P就是有用点的从0到P.

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std; 
struct pp
{
    long long s[105][105];  
}h,_2M[32];
struct node
{
    int s[4],Fail,w;
    bool word;
}a[201];
int m,n,i,g,len,p,point[105];
long long ans;
char s[15];
queue<int> myqueue;
int turn(char c)
{
    if (c=='A') return 0;
    if (c=='G') return 1;
    if (c=='C') return 2;
    return 3;
}
void Built_Trie(int h,int t)
{
    int k=turn(s[t]);
    if (t==len)
    {
         a[h].word=true;
         return;
    }
    if (!a[h].s[k])
    {
         g++;
         a[h].s[k]=g;
    }
    Built_Trie(a[h].s[k],t+1);
}
int UpdateFail(int h,int k)
{
    if (a[h].s[k]) return a[h].s[k];
    else
    if (!h) return h;
    else return UpdateFail(a[h].Fail,k);
}
void Built_AC_Automation()
{
    int h,i;
    while (!myqueue.empty()) myqueue.pop();
    myqueue.push(0);
    while (!myqueue.empty())
    {
         h=myqueue.front();
         myqueue.pop();
         for (i=0;i<4;i++)
         if (a[h].s[i])
         {
               if (!h) a[a[h].s[i]].Fail=h;
               else
               a[a[h].s[i]].Fail=UpdateFail(a[h].Fail,i);
               myqueue.push(a[h].s[i]);
               if (a[a[a[h].s[i]].Fail].word) a[a[h].s[i]].word=true; // 将病毒传递下去...
         }
    }
    return;
}
void Built_Matrix()
{
    int k,i,kk;
    bool f;
    for (k=0;k<=p;k++)  // 扫描所有构造矩阵时的有效点
    {            
          for (i=0;i<4;i++) // 扫描孩子
          {
               kk=point[k];
               f=true;
               while (1)  // kk为头结点也要进去做..但做完后就没必要再调用自己了
               {
                     if (a[kk].s[i]) 
                     {
                           f=false;  // 如果kk在不断的Fail中找到了一个点孩子有i..显然后面就不需要更新h.s[k][0]了..标记
                           if (!a[a[kk].s[i]].word)   // 如果其孩子这个点不为病毒..那么更新
                           {
                               h.s[k][a[a[kk].s[i]].w]++;
                               goto A; 
                           }
                           else goto A;  // 总之进来了就要跳出了...找到了不要继续Fail了..找到了是个病毒也不能继续Fail了..
                     }
                     if (!kk) break;   //  所以在这里判断跳出循环
                     kk=a[kk].Fail;                          
               } 
               if (f) h.s[k][0]++; 
               A: ;
          }
    }
}  
pp Mul(pp a,pp b)    
{
    pp h;
    int i,j,k;
    memset(h.s,0,sizeof(h.s));
    for (k=0;k<=p;k++)
     for (i=0;i<=p;i++)
       for (j=0;j<=p;j++)
         h.s[i][j]=(h.s[i][j]+a.s[i][k]*b.s[k][j])%100000;
    return h;
}
pp GetAnswer(int n)
{
    int i=1,j,m;
    pp ans;
    _2M[i]=h; m=1;
    while (i<=30)
    {
         i++;
         _2M[i]=Mul(_2M[i-1],_2M[i-1]);
         m*=2;
    }  // 得到每个2^K矩阵的值..因为N的范围小于2^31所以做30个足矣
    memset(ans.s,0,sizeof(ans.s));
    for (j=0;j<=p;j++) ans.s[j][j]=1;
    while (n)
    {
         while (m>n) 
         {
               m/=2;
               i--;
         } 
         ans=Mul(ans,_2M[i]);
         n-=m;
    }
    return ans;
}
int main()
{ 
    scanf("%d%d",&m,&n);
    getchar();
    g=0; 
    memset(a,0,sizeof(a));
    while (m--)
    {
         scanf("%s",s);
         len=strlen(s);
         Built_Trie(0,0);
    }
    Built_AC_Automation();
    //------ 去掉病毒点..记录构造矩阵时的有效点..
    p=0;  point[0]=0; a[0].w=0;
    for (i=1;i<=g;i++)
    if (!a[i].word)
    {
           p++;
           point[p]=i;
           a[i].w=p;        
    }
    //------ 去掉病毒点..记录构造矩阵时的有效点..   
    memset(h.s,0,sizeof(h.s));
    Built_Matrix();
    h=GetAnswer(n);
    ans=0;
    for (i=0;i<=p;i++) ans+=h.s[0][i];
    printf("%I64d\n",ans%100000);  
    return 0;
}