HDU 2243（AC自动机+矩阵快速幂）

传送门

题面：

背单词，始终是复习英语的重要环节。在荒废了3年大学生涯后，Lele也终于要开始背单词了。
一天，Lele在某本单词书上看到了一个根据词根来背单词的方法。比如"ab",放在单词前一般表示"相反，变坏，离去"等。

于是Lele想，如果背了N个词根，那这些词根到底会不会在单词里出现呢。更确切的描述是：长度不超过L，只由小写字母组成的，至少包含一个词根的单词，一共可能有多少个呢？这里就不考虑单词是否有实际意义。

比如一共有2个词根 aa 和 ab ，则可能存在104个长度不超过3的单词，分别为
(2个) aa,ab,
(26个)aaa,aab,aac...aaz,
(26个)aba,abb,abc...abz,
(25个)baa,caa,daa...zaa,
(25个)bab,cab,dab...zab。

这个只是很小的情况。而对于其他复杂点的情况，Lele实在是数不出来了，现在就请你帮帮他。

Input

本题目包含多组数据，请处理到文件结束。
每组数据占两行。
第一行有两个正整数N和L。(0<N<6,0<L<2^31)
第二行有N个词根，每个词根仅由小写字母组成，长度不超过5。两个词根中间用一个空格分隔开。

Output

对于每组数据，请在一行里输出一共可能的单词数目。
由于结果可能非常巨大，你只需要输出单词总数模2^64的值。

Sample Input

2 3
aa ab
1 2
a

Sample Output

104
52

题目分析：

又是一个AC自动机的好题。

本质上是bzoj1030和poj2778的综合，只不过数据范围更加大，更加麻烦一些。

首先如果数据范围较小，我们直接可以用一个dp去求出不符合条件的方案数，用总方案数-不合法的方案数即为答案。

但是在这个题中数据范围极大，因此我们必须用类似poj2778中的构造Trie图跑矩阵快速幂的方法去做。

而因为题目中让我们求的是至少包含1个模式串的方案数，因此我们需要求出 $\sum_{k=1}^{m}A^{T}$ （A为邻接矩阵）。因此我们只需要在基础的构建矩阵的过程中使矩阵多开一维，使得第i+1列全为1作为求和。

另外，因为要求至少包含一个模式串的方案数，因此在这种情况下，总方案数为： $S=26+26^{2}+...+26^{m}$ 。显然这个式子直接去快速幂去求必定也会超时，因此我们也得对这个式子进行矩阵优化，对于上述式子有： $S+1=1+26+26^{2}+...+26^{m}$ ，设 $S+1=F(n)$ 有 $F(n)=26*F(n-1)+1$ ，因此F(n)可转化成矩阵形式： $\begin{bmatrix} F(n)\\ 1 \end{bmatrix}=\begin{bmatrix} 26 &1 \\ 0 &1 \end{bmatrix}*\begin{bmatrix} F(n-1)\\ 1 \end{bmatrix}$ ，此后再使用以此矩阵快速幂求解并让求出的两个结果相减即可。

ps：因为题目中要求我们对2^64取模，因此我们只需要将所有变量开成unsigned long long即可（溢出时会自动对2^64取模）。

代码：

#include <bits/stdc++.h>
#define maxn 50
using namespace std;
typedef unsigned long long ll;
int n,m;
char st[maxn];
struct Marix{//矩阵
    ll mo[maxn][maxn],n;
    Marix(){}
    Marix(int _n){
        n=_n;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                mo[i][j]=0;
            }
        }
    }
};
Marix mul(Marix a,Marix b){//矩阵相乘
    Marix res;
    res=Marix(a.n);
    for(int i=0;i<a.n;i++){
        for(int j=0;j<a.n;j++){
            for(int k=0;k<a.n;k++){
                res.mo[i][j]=res.mo[i][j]+a.mo[i][k]*b.mo[k][j];
            }
        }
    }
    return res;
}
Marix powMod(Marix a,ll n){//矩阵快速幂
    Marix res=Marix(a.n);
    for(int i=0;i<a.n;i++){
        res.mo[i][i]=1;
    }
    while(n){
        if(n&1) res=mul(res,a);
        a=mul(a,a);
        n>>=1;
    }
    return res;
}
struct Trie{//AC自动机
    int next[maxn][26],fail[maxn],End[maxn],root,id;
    int newnode(){
        for(int i=0;i<26;i++){
            next[id][i]=-1;
        }
        End[id]=0;
        return id++;
    }
    void init(){
        id=0;
        root=newnode();
    }
    void Insert(char *str){
        int len=strlen(str);
        int now=root;
        for(int i=0;i<len;i++){
            if(next[now][str[i]-'a']==-1){
                next[now][str[i]-'a']=newnode();
            }
            now=next[now][str[i]-'a'];
        }
        End[now]=1;
    }
    void build(){
        queue<int>que;
        for(int i=0;i<26;i++){
            if(next[root][i]==-1){
                next[root][i]=root;
            }
            else{
                fail[next[root][i]]=root;
                que.push(next[root][i]);
            }
        }
        while(!que.empty()){
            int now=que.front();
            que.pop();
            for(int i=0;i<26;i++){
                if(next[now][i]==-1){
                    next[now][i]=next[fail[now]][i];
                }
                else{
                    fail[next[now][i]]=next[fail[now]][i];
                    que.push(next[now][i]);
                }
            }
            End[now]|=End[fail[now]];
        }
    }
    Marix get_Marix(){//构建矩阵
        Marix res=Marix(id+1);
        for(int i=0;i<id;i++){
            for(int j=0;j<26;j++){
                if(End[next[i][j]]) continue;
                res.mo[i][next[i][j]]++;
            }
        }
        for(int i=0;i<id+1;i++){//再多开一维，使得第id+1列全都置为1
            res.mo[i][id]=1;
        }
        return res;
    }
}ac;
int main()
{
    while(~scanf("%d%d",&n,&m)){
        ac.init();
        for(int i=0;i<n;i++){
            scanf("%s",st);
            ac.Insert(st);
        }
        ac.build();
        Marix Mar1=ac.get_Marix();
        ll res=0;
        Mar1=powMod(Mar1,m);
        for(int i=0;i<Mar1.n;i++){
            res+=Mar1.mo[0][i];
        }
        res--;
        Marix Mar2=Marix(2);
        Mar2.mo[0][0]=26;
        Mar2.mo[1][1]=Mar2.mo[0][1]=1;
        Mar2=powMod(Mar2,m);
        ll ans=Mar2.mo[0][0]+Mar2.mo[0][1];
        ans--;
        ans-=res;
        printf("%I64u
",ans);
    }
}