Chlience

【题解】BZOJ 1009 [HNOI2008] GT考试
Problem给定一个长度为 $m$ 的字符串,求不包含这个串的长度为 $n$ 的串有多少个Solution比较懵...
扫描右侧二维码阅读全文
17
2018/12

【题解】BZOJ 1009 [HNOI2008] GT考试

Problem

给定一个长度为 $m$ 的字符串,求不包含这个串的长度为 $n$ 的串有多少个

Solution

比较懵逼

可以考虑下 $DP$,以 $f[i][j]$ 表示当前匹配到第 $i$ 个位置,已经匹配了 $j$ 位的方案数
比较麻烦的是转移,因为已经匹配了 $j$ 个,如果下一个选定的字符和 $j+1$ 位不匹配,不是直接跳到匹配 $0$ 个,而是要往前找能够匹配的最大长度
也就是一个 $KMP$ 的失配问题

那么如果当前位通过 $[0,9]$ 中的任意一个字符能转移到 $f[i+1][k]$ ,那么$f[i+1][k]+=f[i][j]$

发现这个转移貌似和 $i$ 没有任何的关系,所以用矩阵乘法优化掉这一维,总时间复杂度 $O(m^3\log n)$

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int n , m , mod;
char str[30];
int nxt[30];
struct JZ {
    int jz[30][30];
    void clear() {memset(jz , 0 , sizeof(jz));}
    void prepare() {
        clear();
        for(int i = 0 ; i < m ; ++ i)
            jz[i][i] = 1;
    }
    void qpow(int b) {
        JZ ans; ans.prepare();
        while(b) {
            if(b & 1) ans = ans * *this;
            *this = *this * *this;
            b >>= 1;
        }
        *this = ans;
    }
    JZ operator * (const JZ a) const {
        JZ ans;
        ans.clear();
        for(int i = 0 ; i < m ; ++ i)
            for(int j = 0 ; j < m ; ++ j)
                for(int k = 0 ; k < m ; ++ k) {
                    ans.jz[i][j] += 1ll * jz[i][k] * a.jz[k][j] % mod;
                    ans.jz[i][j] %= mod;
                }
        return ans;
    }
}a;
int main() {
    n = read() , m = read() , mod = read();
    scanf("%s" , str);
    int l = - 1 , r = 0;
    nxt[0] = - 1;
    while(r < m) {
        if(l == - 1 || str[l] == str[r]) nxt[++ r] = ++ l;
        else l = nxt[l];
    }
    for(int i = 0 ; i < m ; ++ i) {
        for(int j = 0 ; j <= 9 ; ++ j) {
            int now = i;
            while(now != - 1 && j != str[now] - '0')
                now = nxt[now];
            a.jz[i][now + 1] ++;
        }
    }
    a.qpow(n);
    int ans = 0;
    for(int i = 0 ; i < m ; ++ i) {
        ans += a.jz[0][i];
        ans %= mod;
    }
    printf("%lld\n" , ans);
    return 0;
}
Last modification:December 21st, 2018 at 08:54 pm

Leave a Comment