洛谷P3193 [HNOI2008]GT考試(dp 矩陣乘法)

題意

題目鏈接

Sol

設\(f[i][j]\)表示枚舉到位置串的第i位，當前與未知串的第j位匹配，那麼我們只要保證在轉移的時候永遠不會匹配即可

預處理出已知串的每個位置加上某個字元後能轉移到的位置，矩陣快速冪優化一下

複雜度\(O(M^3 \log n)\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 22;
int N, M, mod,  s[MAXN], trans[MAXN][10], p[MAXN], g[MAXN], base[MAXN];
char ss[MAXN];
template<typename A, typename B> inline void add2(A &x, B y) {
    if(x + y < 0) x = x + y + mod;
    else x = x + y >= mod ? x + y - mod : x + y;
}
int Lim;
struct Ma {
    int m[MAXN][MAXN];
    Ma() {
        memset(m, 0, sizeof(m));
    }
    void init() {
        for(int i = 0; i <= Lim; i++) m[i][i] = 1;
    }
    Ma operator * (const Ma &rhs) const {
        Ma ans;
        for(int i = 0; i <= Lim; i++)
            for(int j = 0; j <= Lim; j++) {
                __int128 tmp = 0;
                for(int k = 0; k <= Lim; k++) tmp += 1ll * m[i][k] * rhs.m[k][j] % mod;
                ans.m[i][j] = tmp % mod;
            }
        return ans;
    }
}f;
void GetNxt() {
    int j = 0;
    for(int i = 0; i <= M; i++) {
        if(i > 1) {
            while(j && s[i] != s[j + 1]) j = p[j];
            if(s[i] == s[j + 1]) j++;
            p[i] = j;
        }
        for(int t = 0; t <= 9; t++) {
            int k = i;
            while(k && t != s[k + 1]) k = p[k];
            if(t == s[k + 1]) k++;
            trans[i][t] = k;
        }
    }
}
Ma MPow(Ma a, int p) {
    Ma base; base.init();
    while(p) {
        if(p & 1) base = base * a;
         a = a * a; p >>= 1;    
    }
    return base;
}
int main() {
    cin >> N >> M >> mod; Lim = M + 1;
    scanf("%s", ss + 1);
    for(int i = 1; i <= M; i++) s[i] = ss[i] - '0';
    for(int i = 0; i <= 9; i++) g[i == s[1]]++;
    GetNxt();
    for(int j = 0; j <= M; j++) 
        for(int k = 0; k <= 9; k++) 
            if(trans[j][k] != M)
                f.m[trans[j][k]][j]++;
    Ma tmp = MPow(f, N - 1);
    for(int i = 0; i <= Lim; i++) 
        for(int j = 0; j <= Lim; j++)
            add2(base[i], 1ll * tmp.m[i][j] * g[j] % mod);
    int ans = 0;
    for(int i = 0; i <= M - 1; i++) add2(ans, base[i]);
    cout << ans;
    return 0;
}
/*
4 3 100
121
*/