[BZOJ1009][HNOI2008]GT考试 AC自动机+矩阵乘法


原题链接
有一个n位数字串,要求里面不能出现一个给出的不吉利串,求方案数mod k.
n小时明显可以trie图上DP,现在n有10^9,则观察到每次转移时相当于把DP值看作行向量,然后乘以trie图的邻接矩阵,因此可以使用矩阵快速幂加速转移.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 30
using namespace std;
int n,m,mod;
char str[N];
struct Node
{
    int x,y,a[N][N];
    Node(){x=y=0;memset(a,0,sizeof a);}
}s,mat;
inline Node operator*(const Node &a,const Node &b)
{
    Node re=Node();
    re.x=a.x,re.y=a.y;
    for(int j,k,i=0;i<re.x;++i)
        for(j=0;j<re.y;++j)
            for(k=0;k<a.y;++k)re.a[i][j]=(re.a[i][j]+a.a[i][k]*b.a[k][j])%mod;
    return re;
}
inline Node quick_pow(Node a,int b)
{
    Node re=Node();
    re.x=re.y=a.x;
    for(int i=0;i<re.x;++i)re.a[i][i]=1;
    while(b)
    {
        if(b&1)re=re*a;
        a=a*a;
        b>>=1;
    }
    return re;
}
int ch[N][10],fail[N],tot=1;
void build_trie()
{
    int len=strlen(str),i,x=1;
    for(i=0;i<len;++i)
    {
        if(!ch[x][str[i]-'0'])ch[x][str[i]-'0']=++tot;
        x=ch[x][str[i]-'0'];
    }
}
int q[N],l=1,r;
void build_fail()
{
    int x,i;
    for(i=0;i<10;++i)
    {
        if(!ch[1][i])ch[1][i]=1;
        else fail[ch[1][i]]=1,q[++r]=ch[1][i];
    }
    while(l<=r)
    {
        x=q[l++];
        for(i=0;i<10;++i)
        {
            if(!ch[x][i])ch[x][i]=ch[fail[x]][i];
            else fail[ch[x][i]]=ch[fail[x]][i],q[++r]=ch[x][i];
        }
    }
}
void build_mat()
{
    s.x=1,s.y=tot;
    s.a[0][0]=1;
    mat.x=mat.y=tot;
    for(int j,i=1;i<tot;++i)
    {
        for(j=0;j<10;++j)if(ch[i][j]!=tot)mat.a[i-1][ch[i][j]-1]++;
    }
}
int calc()
{
    Node re=s*quick_pow(mat,n);
    int ans=0;
    for(int i=0;i<re.y;++i)ans=(ans+re.a[0][i])%mod;
    return ans;
}
int main()
{
    cin>>n>>m>>mod;
    scanf("%s",str);
    build_trie();
    build_fail();
    build_mat();
    cout<<calc();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注