BZOJ1009:[HNOI2008]GT考试(AC自动机,矩乘DP)

时间：2021-05-22 05:16:55

Description

　　阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。
他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为
0

Input

　　第一行输入N,M,K.接下来一行输入M位的数。 N<=10^9,M<=20,K<=1000

Output

　　阿申想知道不出现不吉利数字的号码有多少种，输出模K取余的结果.

Sample Input

4 3 100
111

Sample Output

81

Solution

好题。不看题解不会写题系列。
虽然AC自动机的题解本来就没几篇我还一篇都没看懂
一开始口胡的写法是对的不过因为一个小瑕疵写挂了
建议先写过BZOJ1030文本生成器再来写这个题
不然这个题解可能看不懂
而且因为我比较菜不会的东西太多所以这个题解可能很长……
 
考虑暴力，我们会发现这个题和我做过的BZOJ1030好像几乎一模一样……
就连DP式子都一样
只不过N太大了没法转移是么……
贴一段文本生成器的AC代码。
for (int i=1;i<=m;++i)
    for (int j=0;j<=sz;++j)
        for (int k=0;k<26;++k)
            if (!End[Son[j][k]])
                (f[i][Son[j][k]]+=f[i-1][j])%=MOD;
我们发现外层的m(也就是本题的N)循环的时候，里面两个循环每次进行的转移都是机械一样的。
都是根据父亲的状态来推儿子的状态。
这样的话，我们就可以用矩阵快速幂来优化了。

举个例子
4 3 100
111
这是样例。
我们将初始矩阵start定义为[1,0,0]，这对应的是文本生成器一题中的初始化f[0][0]=1;
然后将x节点与x的所有儿子节点在转移矩阵a中a[x][son]+=1
这样在矩乘转移的时候我们就可以把父亲的状态推到儿子了
最后答案即为start*a^n

因为很容易发现,start是f[0][]的所有状态
start*a是f[1][]的所有状态
那么start*a^n即为f[n][]的所有状态
将start*a^n矩阵里的所有数值加起来即为所求答案。
orz感觉自己已经是一条咸鱼了

对了送组数据:
1000000000 19 9973
1010100110011000001
5753

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<queue>

 #define N (10005)

 using namespace std;

 int Son[N][],End[N],Fail[N];

 int n,m,sz,MOD;

 char s[N];

 queue<int>q;

 struct Matrix

 {

     int m[][];

     void clear(){memset(m,,sizeof(m));};

 };

 Matrix operator * (Matrix a,Matrix b)

 {

     Matrix ans; ans.clear();

     for (int i=; i<=sz+; ++i)

         for (int j=; j<=sz+; ++j)

             for (int k=; k<=sz+; ++k)

                 (ans.m[i][j]+=a.m[i][k]*b.m[k][j])%=MOD;

     return ans;

 }

 Matrix Qpow(Matrix a,int p)

 {

     Matrix ans; ans.clear();

     for (int i=; i<=sz+; ++i) ans.m[i][i]=;

     while (p)

     {

         if (p&) ans=ans*a;

         a=a*a; p>>=;

     }

     return ans;

 }

 void Insert(char s[])

 {

     int now=,len=strlen(s);

     for (int i=; i<len; ++i)

     {

         int x=s[i]-'';

         if (!Son[now][x]) Son[now][x]=++sz;

         now=Son[now][x];

     }

     End[now]|=;

 }

 void Build_Fail()

 {

     for (int i=; i<; ++i)

         if (Son[][i])

             q.push(Son[][i]);

     while (!q.empty())

     {

         int now=q.front();

         q.pop();

         for (int i=; i<; ++i)

         {

             if (!Son[now][i])

             {

                 Son[now][i]=Son[Fail[now]][i];

                 continue;

             }

             End[Son[now][i]]|=End[Son[Fail[now]][i]];

             Fail[Son[now][i]]=Son[Fail[now]][i];

             q.push(Son[now][i]);

         }

     }

 }

 int main()

 {

     Matrix a; a.clear();

     Matrix start; start.clear();

     start.m[][]=;

     scanf("%d%d%d",&n,&m,&MOD);

     scanf("%s",s),Insert(s);

     Build_Fail();

     for (int i=;i<=sz;++i)

         for (int j=;j<;++j)

             if (!End[Son[i][j]])

                 a.m[i+][Son[i][j]+]++;

     a=Qpow(a,n);

     a=start*a;

     int ans=;

     for (int i=;i<=sz+;++i)

         (ans+=a.m[][i])%=MOD;

     printf("%d",ans);

 }

相关文章