【题目链接】 

 

【题目大意】

　　给出一些字符串，求不包含这些字符串的长度为n的字符串的数量

 

【题解】

　　我们将所有串插入自动机计算match，对于自动机上所有节点构建转移矩阵，

　　对于得到的可达矩阵我们求n长路的数量，统计0到各个点的n长路之和就是答案。

 

【代码】

#include 
     
      #include 
      
       using namespace std;const int N=110;typedef long long LL;LL P=100000LL;struct mat{    int n;    LL num[110][110];    void init0(int t){        n=t;        for(int i=0;i
       
        0){            if(t&1)ans=ans*now;            now=now*now;            t>>=1;        }return ans;    }}mat;namespace AC_DFA{    const int Csize=4;     int tot,son[N][Csize],sum[N],fail[N],q[N],ans[N],match[N];    void Initialize(){        memset(sum,0,sizeof(int)*(tot+1));        memset(ans,0,sizeof(int)*(tot+1));        memset(match,0,sizeof(int)*(tot+1));         memset(fail,0,sizeof(int)*(tot+1));        for(int i=0;i<=tot;i++)for(int j=0;j