BZOJ 1009 [HNOI2008]GT考试

Posted on | Edited on

题意

有多少个n位数字，其中没有出现过A ## 题解 很simple的一个DP就是f[i][j]表示现在字符串长度为i，匹配到A的KMP的状态为j，然后用矩阵乘法优化一下就好了 ## 代码

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <cstdio>
#include <cstring>

int n, m, M;
char s[1000];
int nextx[1000];
int mat[22][22], ans[22][22], z[22][22];
int anss;

void getnextx()
{
	int j = 0;
	for (int i = 2; i <= m; i++)
	{
		while (j && s[j + 1] != s[i])
		{
			j = nextx[j];
		}
		if (s[j + 1] == s[i])
		{
			j++;
		}
		nextx[i] = j;
	}
}

void mul(int x[22][22], int y[22][22])
{
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < m; j++)
		{
			z[i][j] = 0;
		}
	}
	for (int k = 0; k < m; k++)
	{
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < m; j++)
			{
				z[i][j] = (z[i][j] + (long long)x[i][k] * y[k][j] % M) % M;
			}
		}
	}
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < m; j++)
		{
			x[i][j] = z[i][j];
		}
	}
}

int main()
{
	scanf("%d%d%d", &n, &m, &M);
	scanf("%s", s + 1);
	getnextx();
	for (int i = 0; i < m; i++)
	{
		for (char j = '0'; j <= '9'; j++)
		{
			int tmp = i;
			while (tmp && s[tmp + 1] != j)
			{
				tmp = nextx[tmp];
			}
			if (s[tmp + 1] == j)
			{
				tmp++;
			}
			if (tmp != m)
			{
				mat[i][tmp]++;
			}
		}
	}
	for (int i = 0; i < m; i++)
	{
		ans[i][i] = 1;
	}
	while (n)
	{
		if (n & 1)
		{
			mul(ans, mat);
		}
		mul(mat, mat);
		n >>= 1;
	}
	anss = 0;
	for (int i = 0; i < m; i++)
	{
		anss = (anss + ans[0][i]) % M;
	}
	printf("%d\n", anss);
	return 0;
}