• 欢迎光临~

# 洛谷 P3193 [HNOI2008]GT考试

dp+矩阵加速

``````#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

#define fr first
#define se second
#define et0 exit(0);
#define rep(i, a, b) for(int i = (int)(a); i <= (int)(b); i ++)
#define rrep(i, a, b) for(int i = (int)(a); i >= (int)(b); i --)
#define IO ios::sync_with_stdio(false),cin.tie(0);

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef unsigned long long ULL;

const int INF = 0X3f3f3f3f, N = 21;
const double eps = 1e-7, pi = acos(-1);

int n, m, MOD;

int ne[N];

string s;

void mul(int c[][N], int a[][N], int b[][N]) {
int tmp[N][N] = {0};
rep (i, 0, N - 1)
rep (j, 0, N - 1)
rep (k, 0, N - 1)
tmp[i][j] = (tmp[i][j] + 1ll * a[i][k] * b[k][j]) % MOD;

memcpy(c, tmp, sizeof tmp);
}

void work() {
cin >> n >> m >> MOD >> s;
s = '*' + s;

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

int f1[N][N] = {0};
f1[0][0] = 1;
int a1[N][N] = {0};

rep (i, 0, m - 1) {
for (char c = '0'; c <= '9'; c++) {
int u = i;
while (u && s[u + 1] != c) u = ne[u];
if (s[u + 1] == c) u++;
a1[i][u] += 1;
}
}

while (n) {
if (n & 1) mul(f1, f1, a1);
mul(a1, a1, a1);
n >>= 1;
}

int res = 0;
rep (i, 0, m - 1) res = ((LL)res + f1[0][i]) % MOD;
cout << res << endl;
}

signed main() {
IO

int test = 1;

while (test--) {
work();
}

return 0;
}
``````