[BZOJ1009] [HNOI2008] GT考试 (KMP & dp & 矩阵乘法)

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

HINT

Source

Solution

　　$f[i][j]$表示由$i$的数字构成的数串中与不吉利数字刚好匹配$j$位的方案数

　　因为我们只需关心后$j$位是否被匹配，如果在不久的将来有一位失配，那么这一段字符就一定不是给定的数串

　　可以看出来，由$f[i]$转移到$f[i+1]$时，需要借助$KMP$算出，具体方法就是枚举$0\sim 9$，用$\pi$数组算出匹配的位数$k$，$f[i+1][k]$+=$f[i][j]$

　　注意到准考证号位数可以达到$10^9$妈蛋考试时号码都抄不完，$TLE/MLE$无疑

　　由于每一次$f[i]$转移到$f[i+1]$时所有步骤是一样的，所以可以用一个矩阵，用乘法代替一次转移。这样就可以用快速幂优化转移啦

　　构造矩阵暴力即可，注意$f[i][m]$的特殊性，它每次只向$f[i+1][m]$转移。

 #include <bits/stdc++.h>

 using namespace std;

 int mod, pi[];

 struct matrix

 {

     int a[][], n, m;

     matrix() {}

     matrix(int x, int y)

     {

         n = x, m = y;

         memset(a, , sizeof(a));

     }

     matrix operator* (matrix rhs)

     {

         matrix ans(n, rhs.m);

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

             for(int j = ; j < rhs.m; ++j)

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

                     ans.a[i][j] = (ans.a[i][j] + a[i][k] * rhs.a[k][j]) % mod;

         return ans;

     }

     matrix operator^ (int rhs)

     {

         matrix ans(n, n), bs = *this;

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

             ans.a[i][i] = ;

         for(; rhs; rhs >>= , bs = bs * bs)

             if(rhs & ) ans = ans * bs;

         return ans;

     }

 };

 char s[];

 void getpi(int m)

 {

     int j = ;

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

     {

         while(j && s[i] != s[j + ])

             j = pi[j];

         pi[i] = s[i] == s[j + ] ? ++j : j;

     }

 }

 int main()

 {

     int n, m, ans, bs = ;

     cin >> n >> m >> mod >> s + ;

     getpi(m);

     matrix f(, m + ), w(m + , m + );

     f.a[][] = , w.a[m][m] = ;

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

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

         {

             int k = i;

             while(k && j != s[k + ] - )

                 k = pi[k];

             if(j == s[k + ] - ) ++k;

             ++w.a[i][k];

         }

     f = f * (w ^ n);

     for(ans = ; n; n >>= , bs = (bs * bs) % mod)

         if(n & ) ans = (ans * bs) % mod;

     cout << (ans - f.a[][m] + mod) % mod << endl;

     return ;

 }

秒客网