首页 > 代码库 > bzoj 1009:[HNOI2008]GT考试
bzoj 1009:[HNOI2008]GT考试
这道题机房n多人好久之前就A了…… 我到现在才做出来……
一看就是DP＋矩阵乘法，但是一开始递推式推错了…… 正确的递推式应该是二维的……
f[i][j] 表示第准考证到第 i 位匹配了 j 位的方案数
f[i][j] = f[i][j-1] + f[i][k] 第k位可以转移到第 j 位
这就需要枚举 当前位是什么， 同是还需要求一个关于m 的KMP 就可以了
上代码：
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#define M 25using namespace std;int n, m;long long f[M] = {0}, yu;long long a[M][M] = {0}, b[M][M] = {0}, c[M][M];int next[M] = {0};char s[M];void make_next(){ int i = 0, j = -1; next[0] = -1; while (i < m-1) if (j == -1 || s[i] == s[j]) { i++; j++; next[i] = j; } else j = next[j];}void cheng(){ for (int i = 0; i < m; ++i) for (int j = 0; j <= m; ++j) c[i][j] = 0; for (int i = 0; i < m; ++i) for (int j = 0; j < m; ++j) for (int k = 0; k < m; ++k) c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % yu; swap(c, b);}void fan(){ for (int i = 0; i < m; ++i) for (int j = 0; j <= m; ++j) c[i][j] = 0; for (int i = 0; i < m; ++i) for (int j = 0; j < m; ++j) for (int k = 0; k < m; ++k) c[i][j] = (c[i][j] + a[i][k] * a[k][j]) % yu; swap(c, a);}void mi(int n){ for (int i = 0; i < m; ++i) b[i][i] = 1; while (n) { if (n & 1) cheng(); n >>= 1; fan(); } swap(a, b);}int main(){ scanf("%d%d%I64d", &n, &m, &yu); scanf("%s", s); make_next(); f[0] = 1; for (int i = 0; i < m; ++i) //已经匹配 i 位 正在匹配第 i+1 位 { for (int j = ‘0‘; j <= ‘9‘; ++j) // 第 i+1 位是 j if (j == s[i]) a[i+1][i] ++; // success else // fail find the last can pipei { int x = next[i]; while (x != -1 && s[x] != j) x = next[x]; a[x+1][i] ++; } } mi(n); long long ans = 0; for (int i = 0; i < m; ++i) { long long zan = 0; for (int j = 0; j < m; ++j) zan = (zan + f[j] * a[i][j]) % yu; ans = (ans + zan) % yu; } printf("%I64d\n", ans);}
bzoj 1009:[HNOI2008]GT考试
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。