OI

BZOJ 1009: [HNOI2008]GT考试

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

HINT

Source

Solution

首先我们发现答案就是求有多少个长度为N的数字串 不包含A这个子串

求方案数 想到DP：F[i][j]表示考虑了前i位，已经匹配了子串的j位的方案数。

答案就是Sigma F[m][0] + … + F[m][r-1]

怎么转移？

  1. F[*][r]对我们的答案是没有贡献的，因为这已经是不合法的了;

  2. 如果当前失配 则跳到最近的地方继续匹配（KMP的next）;

  3. 假设当前是第j个字符，如果j+‘0’->k，那么F[i][k]可以由F[i-1][j]转移过来。

然后发现这个转移是一个线性递推式，第i次转移和i+1次一样，用矩阵快速幂优化。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <cstdio>
#include <algorithm>
using namespace std;
char str[22];
int n, m, P, ans, next[22], k, ret[22][22], mat[22][22], tmp[22][22];
int main() {
	scanf("%d %d %d", &n, &m, &P);
	scanf("%s", str + 1);
	for (int i = 2; i <= m; ++i) {
		while (k && str[i] != str[k+1]) k = next[k];
		if (str[i] == str[k+1]) ++k;
		next[i] = k;
	}
	for (int j = 0; j < m; ++j)
		for (int x = '0'; x <= '9'; ++x) {
			k = j;
			while (k && x != str[k+1]) k = next[k];
			if (x == str[k+1]) ++k;
			if (k != m) ++mat[k][j];
		}
	for (int i = 0; i < m; ++i) ret[i][i] = 1;
	k = n;
	while (k) {
		if (k & 1) {
			for (int i = 0; i < m; ++i) for (int j = 0; j < m; ++j) { tmp[i][j] = 0; for (int ii = 0; ii < m; ++ii) tmp[i][j] += ret[i][ii] * mat[ii][j]; }
			for (int i = 0; i < m; ++i) for (int j = 0; j < m; ++j) ret[i][j] = tmp[i][j] % P;
		}
		for (int i = 0; i < m; ++i) for (int j = 0; j < m; ++j) { tmp[i][j] = 0; for (int ii = 0; ii < m; ++ii) tmp[i][j] += mat[i][ii] * mat[ii][j]; }
		for (int i = 0; i < m; ++i) for (int j = 0; j < m; ++j) mat[i][j] = tmp[i][j] % P;
		k >>= 1;
	}
	for (int i = 0; i < m; ++i)
		ans += ret[i][0];
	printf("%d", ans % P);
}