首页 > 代码库 > _bzoj1009 [HNOI2008]GT考试【矩阵加速dp】
_bzoj1009 [HNOI2008]GT考试【矩阵加速dp】
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1009
比较不错的一道题,令f(i, j)表示考号匹配到i位,后j位为不吉利串的前j位,那么对于每一个状态,都是上一个状态的线性组合,所以可以用矩阵来加速。
#include <cstdio> #include <cstring> const int maxn = 1000000005, maxm = 25; int n, m, p, mtx[maxm][maxm], trie[maxm][10], fail[maxm], trans[maxm][maxm], tem[maxm][maxm], ans; char unf[maxm]; inline void mul(int aa[maxm][maxm], int ss[maxm][maxm]) { memset((void*)tem, 0, sizeof tem); for (int i = 0; i < m; ++i) { for (int j = 0; j < m; ++j) { for (int k = 0; k < m; ++k) { tem[i][j] = (tem[i][j] + aa[i][k] * ss[k][j]) % p; } } } memcpy((void*)aa, (void*)tem, sizeof tem); } inline void poww(int mi) { int i; for (i = 31; mi >> i & 1 ^ 1; --i); memcpy((void*)trans, (void*)mtx, sizeof mtx); for (--i; ~i; --i) { mul(trans, trans); if (mi >> i & 1) { mul(trans, mtx); } } } int main(void) { //freopen("in.txt", "r", stdin); scanf("%d%d%d", &n, &m, &p); scanf("%s", unf + 1); for (int i = 0; i < m; ++i) { trie[i][unf[i + 1] - ‘0‘] = i + 1; } for (int i = 1; i <= m; ++i) { for (int j = 0; j < 10; ++j) { if (trie[i][j]) { fail[trie[i][j]] = trie[fail[i]][j]; } else { trie[i][j] = trie[fail[i]][j]; } } } for (int i = 0; i < m; ++i) { for (int j = 0; j < 10; ++j) { ++mtx[i][trie[i][j]]; } } poww(n); for (int i = 0; i < m; ++i) { ans = (ans + trans[0][i]) % p; } printf("%d\n", ans); return 0; }
_bzoj1009 [HNOI2008]GT考试【矩阵加速dp】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。