哎哟喂，中文题。。。不说题意了。

首先做过POJ 2778可以知道AC自动机是可以求出长度为L的串中不含病毒串的数量的。

POJ 2778的大概思路就是先用所有给的病毒串建一个AC自动机，然后将AC自动机上所有非单词节点连一个边。

离散数学中有说道，如果矩阵A 中的 [i][j] 表示 i节点通过一条边可以走到j节点的方法数。

那么A*A这个矩阵的[i][j]就表示 i 节点到j 节点通过两条边可以走到j节点的方法数。

既然知道这个方法，我们就明确要求什么。

ans= 26+26^2+26^3+....+26^L - 长度为1不含病毒串的数量-长度为2不含病毒串的数量-...-长度为L不含病毒串的数量。

解决两个问题

对 2^64取模。知道2^64是 long long 的最大值，那么我们直接开成unsigned long long ...然后放心大胆的运算，溢出便是取模。

我们知道矩阵 matrix ^ L 但是要求出所有的和，就要用矩阵里套矩阵。也就是求矩阵的和。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define N 35 using namespace std; typedef unsigned long long ll; const char tab = 'a'; const int max_next = 26; struct trie { struct trie *fail; struct trie *next[max_next]; int isword; int index; }; struct AC { trie *que[100005],*root,ac[100005]; int head,tail; int idx; trie *New() { trie *temp=&ac[idx]; for(int i=0;i
      
       next[i]=NULL; temp->fail=NULL; temp->isword=0; temp->index=idx++; return temp; } void init() { idx=0; root=New(); } void Insert(trie *root,char *word,int len){ trie *t=root; for(int i=0;i
       
        next[word[i]-tab]==NULL) t->next[word[i]-tab]=New(); t=t->next[word[i]-tab]; } t->isword++; } void acbuild(trie *root){ int head=0,tail=0; que[tail++]=root; root->fail=NULL; while(head
        
         next[i]){ if(temp==root)temp->next[i]->fail=root; else { p=temp->fail; while(p!=NULL){ if(p->next[i]){ temp->next[i]->fail=p->next[i]; break; } p=p->fail; } if(p==NULL)temp->next[i]->fail=root; } if(temp->next[i]->fail->isword)temp->next[i]->isword++; que[tail++]=temp->next[i]; } else if(temp==root)temp->next[i]=root; else temp->next[i]=temp->fail->next[i]; } } } void tra() { for(int i=0;i
         
          index); for(int k=0;k
          
           index); puts(""); } } }sa; struct matrix { int r,c; ll data[N][N]; matrix(){} matrix(int _r,int _c):r(_r),c(_c){memset(data,0,sizeof data);} friend matrix operator * (const matrix A,const matrix B) { matrix res; res.r=A.r;res.c=B.c; memset(res.data,0,sizeof res.data); for(int i=0;i
           
            >=1; } return res; } void print() { for(int i=0;i
            
             >=1; } return res; } }; int main() { int n,L; while(scanf("%d%d",&n,&L)!=EOF) { sa.init(); for(int i=1;i<=n;i++) { scanf("%s",word); sa.Insert(sa.root,word,strlen(word)); } sa.acbuild(sa.root); E=matrix(sa.idx,sa.idx); for(int i=0;i
             
              index; if(sa.ac[i].next[d]->isword==0) { origin.data[i][temp]++; } } } } supermatrix A; A.ret[0][0]=A.ret[0][1]=E; A.ret[1][0]=zero; A.ret[1][1]=origin; A=A^L; supermatrix f; f.ret[0][0]=f.ret[0][1]=f.ret[1][1]=zero; f.ret[1][0]=origin; matrix fans=A.ret[0][0]*zero+A.ret[0][1]*origin; ll ans=0; for(int i=0;i