洛谷P3193 [HNOI2008]GT考试 题解

题目链接：P3193 [HNOI2008]GT考试

题意：

阿申准备报名参加 GT 考试，准考证号为 \(N\) 位数\(X_1,X_2…X_n(0\le X_i\le9)\)，他不希望准考证号上出现不吉利的数字。 他的不吉利数字\(A_1,A_2…A_m(0\le A_i\le 9)\) 有 \(M\) 位，不出现是指 \(X_1,X_2…X_n\) 中没有恰好一段等于 \(A_1,A_2…A_m\)，\(A_1\) 和\(X_1\) 可以为 \(0\)

\(N\leq10^9,M\leq20,K\leq1000\)

显然是矩阵快速幂优化dp（看数据范围）。

设 \(f_{i,j}\) 表示考虑到第 \(i\) 个数，匹配到 \(X\) 的第 \(j\) 位时的方案数，则 \[ f_{i,j} = \sum_{k=0}^{9}f_{i-1,p} \] 注意这里的 \(0\le j < m\) ，因为我们不能让它包含完整的 \(X\) 。

这个 \(p\) 不一定是 \(0\) 或 \(j-1\) ，根据KMP的性质可以很容易发现。

看上去这个可以用KMP来搞搞，又长的很像矩阵快速幂的题目

于是尝试套路地构造出预处理数组 \(g_{i,j}\) ，以产生矩阵快速幂的形式

设 \(g_{i,j}\) 表示匹配到 \(X\) 的第 \(i\) 位，有多少种加字符 \(0\sim9\) 的方法可以使其匹配到 \(j\)

注意到题目中 \(X_1\) 是可以为 \(0\) 的，因此不用单独考虑前导零的问题，则 \[ f_{i,j} = \sum_{k=0}^{m-1} f_{i-1,k}\times g_{k,j} \] 注意这里 \(k\) 的意义改变为了：枚举已经匹配的长度，尝试加一个字符转移至 \(j\) 。

然后把式子看成这样的形式 \(f^{i}_{j} =\sum f^{i-1}_{k} \times g_{k,j}\) ，显然与矩阵乘法的定义相同

我们把 \(f\) 和 \(g\) 看作两个矩阵（注意 \(f\) 是行矩阵），则有 \[ f^{k} = f^{k-1} \times g \] 则 \[ f^k=g^k \] 然后我们矩阵快速幂求一下就好啦

最后答案就是 \(\sum\limits_{i=0}^{m-1} f^{n}_{i}\) ，没有 \(m-1\) 的原因是，不能包含 \(m\)

时间复杂度 \(O(m^3 \log n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(25)
typedef vector< vector <int> > mat;

char s[N];
int n,m,mod,fail[N];
void add(int &x,int y){ (x+=y) >= mod ? x-=mod : 0;}
mat mul(mat A,mat B)
{
    int n=A.size(),m=A[0].size(),p=B[0].size();
    mat C(n,vector<int>(p));
    for(int i=0; i<m; i++)
        for(int j=0; j<n; j++)
            for(int k=0; k<p; k++)
                add(C[i][j],A[i][k]*B[k][j]%mod);
    return C;
}
mat qpow(mat A,int b)
{
    int n=max(A.size(),A[0].size());
    mat B(n,vector<int>(n));
    for(int i=0; i<n; i++) B[i][i]=1;
    for(; b; b>>=1)
    {
        if(b&1) B=mul(B,A);
        A=mul(A,A);
    }
    return B;
}
mat kmp()
{
    for(int i=2,j=0; i<=m; i++)
    {
        while(j&&s[i]!=s[j+1]) j=fail[j];
        if(s[i]==s[j+1])++j;
        fail[i]=j;
    }
    mat A(m,vector<int>(m));
    for(int i=0,j; i<m; i++)
        for(int c='0'; c<='9'; c++)
        {
            j=i; while(j&&s[j+1]!=c) j=fail[j];
            if(s[j+1]==c) ++j;
            add(A[i][j],1);
        }
    return A;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> mod >> (s+1);
    mat G=kmp(); G=qpow(G,n);
    int res=0;
    for(int i=0; i<m; i++) add(res,G[0][i]);
    cout << res << '\n';
    return 0;
}