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]);


    }
}