HDOJ-2243AC自动机.等比矩阵求和

题目是要说小于L长度的由小写字母组成的字符串有多少个包含所给的串...

从正方向想..要求出包含的..并且还要踢去重复包含的..又要加上被多踢的..整个一容斥问题了...但这题明显是不可行的...那么换个角度..先求出总共小于L的单词数(26^1+26^2+26^3+...26^L)..然后再减去不包括所给字符串的单词...相当于把每个单词看成POJ2778中的病毒...

但还有个问题...如何求出矩阵A的 A+A^2+A^3+....A^L .. 这里参考了​​http://www.cppblog.com/baby-fly/archive/2009/08/18/93686.html​​所构造的矩阵...

等比矩阵求和，有经典算法，假定原矩阵为A，阶数为n，那么构造一个阶数为2n的矩阵，如下
| A E | 其中O代表O矩阵，E代表单位矩阵，这样，求出的K次矩阵的右上n子矩阵正好是
| O E | 等比矩阵的K项和，这种构造法比我实现的两次二分快了4倍左右。

这里有个错误要注意...求出K次矩阵的右上子矩阵应该是K-1项的和...

Program:

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<queue>
#define ull unsigned __int64
using namespace std; 
struct node1
{
       int son[26],fail;
       bool word;
}point[205];
struct node
{
       ull s[65][65];
}temp,h,_2M[35],T; 
char s[7];
queue<int> myqueue;
ull ans;
int n,l,m;
void Built_Trie()
{  
        int i,len,h;
        memset(point[0].son,0,sizeof(point[0].son));
        point[0].word=point[0].fail=0;
        m=0;
        while (n--)
        {
               scanf("%s",s);
               len=strlen(s);
               h=0;
               for (i=0;i<len;i++)
               {
                      if (!point[h].son[s[i]-'a'])
                      {
                             m++;
                             point[h].son[s[i]-'a']=m;
                             memset(point[m].son,0,sizeof(point[m].son));
                             point[m].word=point[m].fail=0;
                      }
                      h=point[h].son[s[i]-'a'];
                      if (point[h].word) break;
               }
               point[h].word=true;
        }
        return;
}
void Built_AC_Automation()
{
       int i,h,k;
       while (!myqueue.empty()) myqueue.pop();
       for (i=0;i<26;i++)
           if (point[0].son[i]) myqueue.push(point[0].son[i]);
       while (!myqueue.empty())
       {
               h=myqueue.front();
               myqueue.pop();
               for (i=0;i<26;i++)
               if (point[h].son[i])
               {
                       k=point[h].fail;
                       while (k && !point[k].son[i]) k=point[k].fail;
                       point[point[h].son[i]].fail=point[k].son[i];
                       if (point[point[k].son[i]].word)
                          point[point[h].son[i]].word=true;
                       myqueue.push(point[h].son[i]);
               }
       }
       return;              
}
void Output_Matrix(node h)
{
       int i,j;
       for (i=1;i<=2*m;i++)
       {
             for (j=1;j<=2*m;j++) printf("%3I64u",h.s[i][j]);
             printf("\n");
       }
}
void Built_Matrix()
{
       int i,j,k;
       memset(h.s,0,sizeof(h.s));
       for (i=0;i<=m;i++)
          if (!point[i].word)
             for (j=0;j<26;j++)
             {
                      k=i;
                      while (k && !point[k].son[j])  k=point[k].fail; 
                      if (!point[point[k].son[j]].word) 
                         h.s[i+1][point[k].son[j]+1]++; 
             }
       m++;
       j=1;
       for (i=1;i<=m;i++) 
       {
             h.s[j][i+m]=h.s[j+m][i+m]=1;
             j++;
       }     
       return;
}
node Matrix_Mul(node a,node b,int m)
{
       int i,j,k;
       memset(temp.s,0,sizeof(temp.s));
       for (k=1;k<=2*m;k++)
          for (i=1;i<=2*m;i++)
             for (j=1;j<=2*m;j++)
                temp.s[i][j]+=a.s[i][k]*b.s[k][j];
       return temp;
}
void getmatrix(node h,int m,int l)
{
       int p=0,i;
       l++;
       ull k;
       _2M[0]=h;
       k=1;
       for (i=1;i<=30;i++) 
       {
             _2M[i]=Matrix_Mul(_2M[i-1],_2M[i-1],m);
             k*=2; 
             p++;
             if (k>=l) break;
       }
       memset(T.s,0,sizeof(T.s));
       for (i=1;i<=2*m;i++) T.s[i][i]=1;
       while (l)
       {
              while (k>l)   
              {     
                    k/=2;  
                    p--;  
              }   
              T=Matrix_Mul(T,_2M[p],m);  
              l-=k;  
       }  
       return;
}
void _26P(int l)
{  
       node h;
       ans=0;
       h.s[1][1]=26; h.s[1][2]=1; h.s[2][1]=0; h.s[2][2]=1;
       getmatrix(h,2,l);
       ans=T.s[1][2]; 
}
void getdata()
{ 
       _26P(l); 
       getmatrix(h,m,l);
       for (int i=m+1;i<=2*m;i++) ans-=T.s[1][i];   
       return;
}
int main()
{
       while (~scanf("%d%d",&n,&l))
       {
               Built_Trie();
               Built_AC_Automation();
               Built_Matrix();                
               getdata();
               printf("%I64u\n",ans);
       }
       return 0;
}