洛谷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;
}