水题笔记 [HNOI2008]GT考试 [KMP, 矩阵, DP]

Roll boys~ Roll boys roll!

从R1回来了突然发现我联赛和省选前的一个月都一个题没写

不知道怎么回事就是不想学习←_←

懵逼的题目

BZOJ

扯淡的题解

我们发现这题和我一个月之前做的那个题肥肠像

除了\(n\)有点大

那就矩乘优化一下就好了因为如果已经匹配的位数和当前位是什么都确定了的话转移也是确定的

沙茶的代码

我居然一遍写对了

~~除了忘给矩阵里的n和m赋值了~~

/**************************************************************
    Problem: 1009
    User: Cansult
    Language: C++
    Result: Accepted
    Time:56 ms
    Memory:1460 kb
****************************************************************/
 
// 构造21 * 21的矩阵 对于每一行 除了要转移过去的地方全部置为0 
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000000000 + 5)
#define MAXM (20 + 5)
using namespace std;
struct matrix {
    int n, m, zh[MAXM][MAXM];
    matrix() { memset(zh, 0, sizeof(zh)); }
} m1, ma, f;
int n, m, p, nex[MAXM], ans;
char s[MAXM];
void init() {
    m1.n = m1.m = m;
    for (int i = 0; i < m; i++) m1.zh[i][i] = 1;
    f.n = 1, f.m = m;
    f.zh[0][0] = 1;
    for (int i = 1, j = 0; i < m; i++) {
        j = nex[i];
        while (j && s[j] != s[i]) j = nex[j]; 
        nex[i + 1] = (s[i] == s[j]) ? (j + 1) : 0;
    }
    ma.n = ma.m = m;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < 10; j++) {
            int ndq = i;
            while (ndq && s[ndq] - '0' != j) ndq = nex[ndq];
            if (s[ndq] - '0' == j) ++ndq;
            ++ma.zh[i][ndq];
        }
    }
}
matrix tim(matrix x, matrix y) {
    matrix re;
    re.n = x.n, re.m = y.m;
    for (int i = 0; i < re.n; i++)
        for (int j = 0; j < re.m; j++)
            for (int k = 0; k < x.m; k++)
                re.zh[i][j] += x.zh[i][k] * y.zh[k][j] % p, re.zh[i][j] %= p;
    return re;
}
matrix ksm(int b) {
    if (!b) return m1;
    matrix re = ksm(b >> 1);
    re = tim(re, re);
    if (b & 1) re = tim(re, ma);
    return re;
}
int main() {
    scanf("%d%d%d", &n, &m, &p);
    scanf("%s", s);
    init();
    f = tim(f, ksm(n));
    for (int i = 0; i < m; i++) ans += f.zh[0][i], ans %= p;
    printf("%d", ans);
    return 0;
}

懵逼的题目

扯淡的 题解

沙茶的 代码

扯淡的题解

沙茶的代码