洛谷 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;
}