题目大意：

构造一个串使得有两个以及两个以上的目标串。长度为L的所有串中有多少个这样的串。

思路分析：

用所有的数量减去只有1个和没有目标串的数量就是答案了。

如果数据很小，可以用dp解。dp[i][j][k] 表示长度为i，走到自动机的j，有k个目标串的数量。

转移便是。

if(j->next[d] ->isword) dp[i+1][j->next][1] += dp[i][j][0].

else dp[i+1][j->next][0]+=dp[i][j][0],dp[i+1][j->next][1] += dp[i][j][1]...

现在长度达到百万。

所以用矩阵优化。

设自动机的节点数量为idx，那么就开一个（2*idx，2*idx）的矩阵。

如果i

如果i idx 表示 开始在i的时候没有目标串，走到j有了一个。

后面同理。。。

那么构造这个矩阵便是按照上面的dp方程类似构造。

if(j->next[d]->isword)matrix [i][j->next->index+idx]++; 开始的时候没有，走过来加一个

else matrix [i][j]++,matrix [i+idx][j+idx] 开始的时候没有，走到j也没有 和 开始的时候有一个，走到j还是一个。

矩阵的构造是难= =

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define N 75 using namespace std; const int mod = 10007; const char tab = 'a'; const int max_next = 4; int rev[256]; 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[rev[word[i]]]==NULL) t->next[rev[word[i]]]=New(); t=t->next[rev[word[i]]]; } 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; int 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
            
             index; if(sa.ac[i].next[j]->isword) origin.data[i][temp+sa.idx]++; else origin.data[i][temp]++,origin.data[i+sa.idx][temp+sa.idx]++; } } origin.print(); origin=origin^L; int ans=1; int x=4; int t=L; while(t) { if(t&1)ans=(ans*x)%mod; x=(x*x)%mod; t>>=1; } for(int i=0;i<2*sa.idx;i++) { ans-=origin.data[0][i]; ans=(ans+mod)%mod; } printf("%d\n",ans); } return 0; }