P3193 [HNOI2008]GT考试 题解(kmp+矩阵快速幂)

题目链接

题目思路

设\(dp[i][j]\)表示长度为\(i\)的字符串匹配长度为\(j\)的字符串

如果第\(i+1\)个字符等于\(s[j+1]\) 那么就转移到\(dp[i+1][j+1]\)

否则根据\(kmp\)那么此时\(j=nxt[j]\) 然后再递归判断

数据这么大要往矩阵快速幂的思路去思考

设\(base.a[i][j]\) 表示有多少种方案数使得加一个字符使得匹配\(i\)个字符变为\(j\)个字符

那么\(ans.a[i][j]=\sum_{k=0}^{k=m-1}ans.a[i][k]\times base.a[k][j]\)

然后再使用矩阵快速幂加速

对于矩阵快速幂的理解

以我们把每一行\(ans[i][j]\)抽象成只有一行，列数为\(m-1\)的\(F[i]\)

最后即为\(F[i]=F[i-1]*base^n\)

我感觉这个题目太多细节了

实在太妙了

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef pair<int,int> pii;
#define fi first
#define se second
#define debug printf("aaaaaaaaaaa\n");
const int maxn=20+5,inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,m,k,mod;
char s[maxn];
int nxt[maxn];
struct matrix{
    ll a[maxn][maxn];
}base,ans,last;
matrix mul(matrix a,matrix b,int n){
    matrix temp;
    memset(temp.a,0,sizeof(temp.a)); //一定1要清空
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                temp.a[i][k]+=(a.a[i][j])*(b.a[j][k]);
                temp.a[i][k]%=mod;
            }
        }
    }
    return temp;
}
void qpow(ll n,ll b){
    while(b){
        if(b&1){
            ans=mul(ans,base,n);
        }
        base=mul(base,base,n);
        b=b>>1;
    }
}

void getnext(){
    for(int i=2,j=0;i<=m;i++){
        while(j&&s[j+1]!=s[i]){
            j=nxt[j];
        }
        if(s[j+1]==s[i]) j++;
        nxt[i]=j;
    }
}
void getbase(){
    for(int i=0;i<m;i++){ //现在匹配了i位
        for(int j=0;j<=9;j++){
            int x=i;
            while(x&&j!=s[x+1]-'0'){
                x=nxt[x];
            }
            if(j==s[x+1]-'0'){
                x++;
            }
            if(x!=m){
                base.a[i][x]=(base.a[i][x]+1)%mod;
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&mod);
    scanf("%s",s+1);
    getnext();
    getbase();
    for(int i=0;i<m;i++){
        ans.a[i][i]=1;
    }
    qpow(m,n);
    ll pr=0;
    last.a[0][0]=1;
    last=mul(last,ans,m);
    for(int i=0;i<m;i++){
        pr=(pr+last.a[0][i])%mod;
    }
    printf("%lld\n",pr);
    return 0;
}