BZOJ 1009 HNOI 2008 GT考试 递推+矩乘

1009: [HNOI2008]GT考试

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 3679  Solved: 2254
[Submit][Status][Discuss]

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

如果n很小的话，可以直接做数位DP，但是现在n很大，需要用到矩乘。

设F[i][j]表示准考证号前i位中匹配到不吉利数串的第j个的方案数。

我们很容易发现，F数组存在一定的转移关系。

转移时考虑当前匹配到不吉利串的第i个，下一个数字填0~9时，转移到匹配到不吉利串的第j个，匹配过程可以KMP，这样就可以构造出转移矩阵。

Code

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <string>

 #include <algorithm>

 using namespace std;

 #define REP(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i)

 #define mset(a, b) memset(a, b, sizeof(a))

 const int maxn = ;

 int n, m, MOD;

 char s[maxn];

 int nxt[maxn];

 struct Matrix

 {

     int mat[maxn][maxn];

     Matrix() { mset(mat, ); }

     Matrix operator * (const Matrix &AI) const

     {

         Matrix ret;

         REP(i, , m-)

             REP(j, , m-)

             {

                 ret.mat[i][j] = ;

                 REP(k, , m-) (ret.mat[i][j] += mat[i][k]*AI.mat[k][j]) %= MOD;

             }

         return ret;

     }

 }A, B;

 int main()

 {

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

     scanf("%s", s+);

     int j = ; nxt[] = ;

     REP(i, , m)

     {

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

         if (s[j+] == s[i]) j ++;

         nxt[i] = j;

     }

     REP(i, , m-)

         REP(j, , )

         {

             int t = i;

             while (t >  && s[t+]-'' != j) t = nxt[t];

             if (s[t+]-'' == j) t ++;

             if (t != m) B.mat[t][i] = (B.mat[t][i]+)%MOD;

         }

     REP(i, , m-) A.mat[i][i] = ;

     while (n > )

     {

         if (n&) A = A*B;

         B = B*B;

         n >>= ;

     }

     int ans = ;

     REP(i, , m-) ans = (ans+A.mat[i][])%MOD;

     printf("%d\n", ans);

     return ;

 }