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

#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);
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据