[bzoj1009](HNOI2008)GT考试 (kmp+矩阵快速幂加速递推)

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位的数。 100%数据N<=10^9,M<=20,K<=1000 40%数据N<=1000 10%数据N<=6

Output

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

Sample Input

4 3 100
111

Sample Output

分析

“——然而谁也看不穿HNOI……”= =谁知道hnoi2008连出两道矩阵快速幂是什么心态呢……

这里可以先用kmp之类的字符串算法预处理出“不吉利串”中的所有前缀之间的转移边，构造一个N*N的矩阵，其中A(i,j)表示由不吉利串的i前缀转移到j前缀的方法数。注意矩阵的坐标范围为0~N-1，即这一矩阵是在所有非匹配状态之间进行的转移，因此最终转移出的所有状态都满足提议。所以我们最后做一个矩阵快速幂，右边乘上N位的全1列向量，结果取第0行即可。

  1 /**************************************************************
  2     Problem: 1009
  3     User: AsmDef
  4     Language: C++
  5     Result: Accepted
  6     Time:56 ms
  7     Memory:812 kb
  8 ****************************************************************/
  9
10 #include <cctype>
11 #include <cstdio>
12 using namespace std;
13 template<typename T>inline void getd(T &x){
14     char c = getchar(); bool minus = 0;
15     while(!isdigit(c) && c != '-')c = getchar();
16     if(c == '-')minus = 1, c = getchar();
17     x = c - '0';
18     while(isdigit(c = getchar()))x = x * 10 + c - '0';
19     if(minus)x = -x;
20 }
21 /*========================================================*/
22 const int maxm = 23;
23 int N, M, K, p[maxm][maxm], tmp[maxm][maxm];
24 char St[maxm];
25 inline int bitcnt(int x){
26     x = ((x >> 1) & 0x55555555) + (x & 0x55555555);
27     x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
28     x = ((x >> 4) & 0x0f0f0f0f) + (x & 0x0f0f0f0f);
29     x = ((x >> 8) & 0x00ff00ff) + (x & 0x00ff00ff);
30     x = ((x >> 16) & 0x0000ffff) + (x & 0x0000ffff);
31     return x;
32 }
33 struct Mat{
34     int A[maxm][maxm];
35     void operator *= (const Mat &x){
36         int i, j, k;
37         for(i = 0;i < M;++i)for(j = 0;j < M;++j){
38             tmp[i][j] = 0;
39             for(k = 0;k < M;++k)
40                 tmp[i][j] = (tmp[i][j] + A[i][k] * x.A[k][j]) % K;
41         }
42         for(i = 0;i < M;++i)for(j = 0;j < M;++j)
43             A[i][j] = tmp[i][j];
44     }
45 }Ans, Per;
46 inline void init(){
47     getd(N), getd(M), getd(K);
48     int i, j, k, t, next[maxm];
49     while(!isdigit(St[1] = getchar())); St[1] -= '0';
50     for(i = 2;i <= M;++i)
51         St[i] = getchar() - '0';
52     next[0] = next[1] = 0;
53     for(i = 1;i < M;++i){
54         j = next[i]; k = (1 << 10) - 1;
55         p[i][i+1] = 1; k ^= (1 << St[i+1]);
56         while(j && St[j+1] != St[i+1]){
57             t = 1 << St[j+1];
58             if(k & t)p[i][j+1] = 1, k ^= t;
59             j = next[j];
60         }
61         if(St[j+1] != St[i+1]){
62             next[i+1] = 0;
63             t = 1 << St[1];
64             if(k & t)p[i][1] = 1, k ^= t;
65         }
66         else{
67             next[i+1] = j+1;
68             while(j){
69                 j = next[j];
70                 if(St[j+1] != St[i+1]){
71                     t = 1 << St[j+1];
72                     if(k & t)p[i][j+1] = 1, k ^= t;
73                 }
74             }
75         }
76         p[i][0] = bitcnt(k);
77     }
78     p[0][0] = 9, p[0][1] = 1;
79     for(i = 0;i < M;++i)for(j = 0;j < M;++j)
80         Ans.A[i][j] = Per.A[i][j] = p[i][j];
81 }
82
83 int main(){
84     #if defined DEBUG
85     freopen("test", "r", stdin);
86     #else
87     //freopen("bzoj_1009.in", "r", stdin);
88     //freopen("bzoj_1009.out", "w", stdout);
89     #endif
90     init();
91     if(!N){printf("0 ");return 0;}
92     N -= 1;
93     while(N){
94         if(N & 1)Ans *= Per;
95         Per *= Per;
96         N >>= 1;
97     }
98     **tmp = 0;
99     while(M--)
100         **tmp = (**tmp + Ans.A[0][M]) % K;
101     printf("%d ", **tmp);
102
103     return 0;
104 }

kmp+矩阵快速幂