HDU-2243考研路茫茫 AC自动机 + 矩阵快速幂

hdu-2243
n个模式串，求满足长度小于等于k且至少包含其中一种模式串的串数（只包含

小写字母）
k<2^31-1
多模式串的计数问题，我们用AC自动机来解决
那么问题来了
1）怎么求至少包含一种的串数？
正难则反，我们用所有串数减去一种都不含的就是至少包含一种的方案
2）所有长度小于等于k的串数怎么求？即26+26^2+26 ^3+……26 ^k
首先想到的是利用 等比数列前n项和 a1*(1-q^n)/(1-q)；但本题由于是对2 ^64取模，所以我们无法解决逆元的问题，那怎么办呢
！通过枚举k发现 我们要求的F（k）=26F（k-1）+26；！！！
所以可以构建矩阵进行 矩阵快速幂加速

        F.a[0][0]=26;F.a[0][1]=26;
        F.a[1][0]=0;F.a[1][1]=0;

        fd.a[0][0]=26;fd.a[0][1]=0;
        fd.a[1][0]=1;fd.a[1][1]=1;
        F=F*qp(fd,k-1);

3）一种都不含的串怎么求？
首先对n个模式串建立AC自动机，并建立有向图A[i][j]代表 I 节点到 J 节点一步能走到的方法数其中 所有模式串的结尾节点以及包含所有模式串的节点 都为不可到达点，即所在行和列权值都为0。那么长度为K的串数即为从根节点（0节点）在图中走K部的方法数（即接受K个字母，每接受1个字母相当于在有向图中走一次）
又由引理：在有向图中走K步，相当于这个有向图的邻接矩阵自乘K次
之后我们便可以直接对该矩阵进行快速幂，然后在对第0行求和即可
但是
此题要求所有长度小于等于K的串数
即我们要分别求出所有I=1到K 的和，这里我们同样可以通过构建矩阵来解决

        MAT1 C1,C2;
        for(int i=0;i<=tot+1;i++) for(int j=0;j<=tot+1;j++)
            C1.a[i][j]=C2.a[i][j]=0;
        for(int i=0;i<=tot+1;i++) C2.a[i][tot+1]=1;

        for(int i=0;i<=tot;i++){
            if(is[i]) continue;
            for(int j=0;j<26;j++){
                if(is[trie[i][j]]) continue;
                C1.a[i][trie[i][j]]++;
                C2.a[i][trie[i][j]]++;
            }
        }
        C1=C1*qp(C2,k-1);

具体请看代码

#include<bits/stdc++.h>
#define warn printf("!!!***!\n")
using namespace std;
typedef unsigned long long LL;
typedef pair<int,int>pii;
typedef pair<LL,LL>pll;
const int maxn=1e6+6;
const int mod=1e9+7;
int fail[maxn],trie[maxn][26],is[maxn],tot,n,k;
char s[maxn];
queue<int>q;
struct AC_auto
{
    void init(){
        for(int i=0;i<=tot;i++){
            fail[i]=is[i]=0;
            for(int j=0;j<26;j++){
                trie[i][j]=0;
            }
        }
        tot=0;
        while(!q.empty()) q.pop();
    }
    void add(char *s){
        int len=strlen(s),p=0;
        for(int i=0;i<len;i++){
            int c=s[i]-'a';
            if(!trie[p][c]) trie[p][c]=++tot;
            p=trie[p][c];
        }
        is[p]=1;
    }
    void build_f(){
        for(int i=0;i<26;i++) if(trie[0][i])
            q.push(trie[0][i]);

        while(!q.empty()){
            int f=q.front();q.pop();

            is[f]|=is[fail[f]];
            for(int i=0;i<26;i++){
                if(trie[f][i]){
                    fail[trie[f][i]]=trie[fail[f]][i];
                    q.push(trie[f][i]);
                }
                else trie[f][i]=trie[fail[f]][i];
            }
        }
    }

}ac;
struct MAT1
{
    LL a[55][55];
    MAT1 operator *(const MAT1 &k2) const {
         MAT1 p;
         for(int i=0;i<=tot+1;i++){
            for(int j=0;j<=tot+1;j++){
                p.a[i][j]=0;
                for(int k=0;k<=tot+1;k++){
                    p.a[i][j]+=a[i][k]*k2.a[k][j];
                }
            }
         }
         return p;
    }
};
struct MAT2
{
    LL a[2][2];
    MAT2 operator *(const MAT2 &k2) const {
         MAT2 p;
         for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                p.a[i][j]=0;
                for(int k=0;k<2;k++){
                    p.a[i][j]+=a[i][k]*k2.a[k][j];
                }
            }
         }
         return p;
    }
};
MAT1 qp(MAT1 x,LL y)
{
    MAT1 ans;
    for(int i=0;i<=tot+1;i++) for(int j=0;j<=tot+1;j++)
        ans.a[i][j]=(i==j?1:0);
    while(y){
        if(y&1) ans=ans*x;
        x=x*x;
        y>>=1;
    }
    return ans;
}
MAT2 qp(MAT2 x,LL y)
{
    MAT2 ans;
    for(int i=0;i<2;i++) for(int j=0;j<2;j++)
        ans.a[i][j]=(i==j?1:0);
    while(y){
        if(y&1)ans=ans*x;
        x=x*x;
        y>>=1;
    }
    return ans;
}
int main()
{
    while(~scanf("%d %d",&n,&k)){
        ac.init();
        for(int i=1;i<=n;i++){
            scanf("%s",s);
            ac.add(s);
        }
        ac.build_f();
        MAT2 F,fd;
        F.a[0][0]=26;F.a[0][1]=26;
        F.a[1][0]=0;F.a[1][1]=0;

        fd.a[0][0]=26;fd.a[0][1]=0;
        fd.a[1][0]=1;fd.a[1][1]=1;
        //cout<<n<<','<<k<<endl;
        F=F*qp(fd,k-1);

        //printf("%llu\n",F.a[0][0]);

        MAT1 C1,C2;
        for(int i=0;i<=tot+1;i++) for(int j=0;j<=tot+1;j++)
            C1.a[i][j]=C2.a[i][j]=0;
        for(int i=0;i<=tot+1;i++) C2.a[i][tot+1]=1;

        for(int i=0;i<=tot;i++){
            if(is[i]) continue;
            for(int j=0;j<26;j++){
                if(is[trie[i][j]]) continue;
                C1.a[i][trie[i][j]]++;
                C2.a[i][trie[i][j]]++;
            }
        }

        C1=C1*qp(C2,k-1);

        for(int i=0;i<=tot+1;i++) F.a[0][0]-=C1.a[0][i];

        printf("%llu\n",F.a[0][0]);


    }
}