GT 考试

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2078 字
长度为n的数字串中不出现给定m位数字串的个数
一本通
练习
正文

/*
原题：T1646「一本通 6.5 练习 2」GT 考试
题意：长度为 n 的数字串（每位 0~9）中不出现给定 m 位数字串（不吉利数字）的个数，答案对 K 取模。
思路：对不吉利串做 KMP，以「已匹配的前缀长度」为状态（0~m-1），用失配函数算出每个状态读入各数字的转移。
把这些转移建成 m×m 的计数矩阵，取它的 n 次幂；从状态 0 出发走 n 步后停在各状态的方案数之和即为答案。
复杂度：时间 O(m^3·log n)，空间 O(m^2)
易错点：1) 转移到「已完全匹配」的吸收态要丢弃，不能计入矩阵；
2) 方向别写反：矩阵 M[s][ns] 表示按行取状态做行向量乘法，答案是 Σ(M^n)[0][j]；
3) 每位数字需按 K 取模，K 不保证是质数，用普通累加取模。
*/
#include <bits/stdc++.h>
using namespace std;
long long MODV;
vector<vector<long long>> mul(const vector<vector<long long>>& x,const vector<vector<long long>>& y){
    int n=x.size();
    vector<vector<long long>> r(n,vector<long long>(n,0));
    for(int i=0;i<n;i++){
        for(int k=0;k<n;k++){
            if(x[i][k]==0){
                continue;
            }
            for(int j=0;j<n;j++){
                r[i][j]=(r[i][j]+x[i][k]*y[k][j])%MODV;
            }
        }
    }
    return r;
}
// KMP 失配后下一个状态：当前已匹配 state 位，再读入字符 c
int trans(int state,char c,const string& pat,const vector<int>& pi){
    while(state>0 && pat[state]!=c){
        state=pi[state-1];
    }
    if(pat[state]==c){
        state++;
    }
    return state;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long n;
    int m;
    cin>>n>>m>>MODV;
    string pat;
    cin>>pat;
    vector<int> pi(m,0);
    for(int i=1;i<m;i++){
        int j=pi[i-1];
        while(j>0 && pat[i]!=pat[j]){
            j=pi[j-1];
        }
        if(pat[i]==pat[j]){
            j++;
        }
        pi[i]=j;
    }
    vector<vector<long long>> base(m,vector<long long>(m,0));
    for(int s=0;s<m;s++){
        for(char d='0';d<='9';d++){
            int ns=trans(s,d,pat,pi);
            if(ns<m){
                base[s][ns]=(base[s][ns]+1)%MODV;
            }
        }
    }
    vector<vector<long long>> r(m,vector<long long>(m,0));
    for(int i=0;i<m;i++){
        r[i][i]=1;
    }
    while(n>0){
        if(n&1){
            r=mul(r,base);
        }
        base=mul(base,base);
        n>>=1;
    }
    long long ans=0;
    for(int j=0;j<m;j++){
        ans=(ans+r[0][j])%MODV;
    }
    cout<<ans<<"\n";
    return 0;
}
GT 考试

正文

一本通·提高篇的其它内容
