Roll boys~ Roll boys roll!

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

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

懵逼的题目

BZOJ

扯淡的 题解

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

除了$n$有点大

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

沙茶的 代码

我居然一遍写对了

除了忘给矩阵里的nm赋值了

/**************************************************************
    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;
}

By 准备退役旅游的 Cansult