P3193 [HNOI2008]GT考试

我们有一个搞笑的做法：

$dp[i][sta]$ ，其中 $sta$ 表示后 $M$ 为 $sta$ 的方案数，然后转移也非常简单，每次转移完更新 $sta$ 为 $[\frac{sta}{10}] \t\dfrac10+a[i]$ 即可。

显然这样会炸。

考虑如何压缩后一维的状态。

还是考虑 $Insert$ 函数，对于一个给定的 $j,ch$ ，输出都是唯一的，而且 $j \in [1,M],output\in[1,M]$ 。

这就让我们想到可以压到一个 $M$ 的状态里面。

dp[0][0]=1;
for (register int i=1;i<=n;++i){
    for (register int j=0;j<m;++j){
        for (register char ch='0';ch<='9';++ch){
            int k=Insert(ch,j);
            dp[i][k]=(dp[i-1][j]+dp[i][k])%mod;
        }
     }
}
ans=0;
for (register int i=0;i<m;++i) ans+=dp[n][i];

注意到这个可以使用矩阵快速幂优化。

于是得到以下代码：

#include <bits/stdc++.h>
#define MAXN 1000005
#define MAXM 205
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int dp[MAXN][MAXM],nex[MAXM],n,m,mod;
char s[MAXM];
inline void Build(){
    int j=0;
    for (register int i=2;i<=m;++i){
        while (j&&s[j+1]!=s[i]) j=nex[j];
        if (s[j+1]==s[i]) j++;
        nex[i]=j;
    }
}
inline int Insert(char ch,int j){
    while (j&&ch!=s[j+1]) j=nex[j];
    if (ch==s[j+1]) j++;
    return j;
}
struct Matrix{
    int a[MAXM][MAXM];
}base;
inline Matrix operator * (const Matrix &A,const Matrix &B){
    Matrix C;
    for (register int i=0;i<m;++i){
        for (register int j=0;j<m;++j){
            C.a[i][j]=0;
            for (register int k=0;k<m;++k){
                C.a[i][j]=(C.a[i][j]+1ll*A.a[i][k]*B.a[k][j]%mod)%mod;
            }
        }
    }
    return C;
}
inline void BuildMat(){
    for (register int j=0;j<m;++j){
        for (register char ch='0';ch<='9';++ch){
            int k=Insert(ch,j);
            base.a[j][k]++;
        }
    }
}
inline Matrix ksm(Matrix A,int k){
    Matrix ans=A;k--;
    while (k){
        if (k&1) ans=ans*A;
        A=A*A;
        k>>=1;
    }
    return ans;
}
int main(){
    n=read(),m=read(),mod=read();
    scanf("%s",s+1);
    Build(),BuildMat();
    Matrix ans=ksm(base,n)
    int ret=0;
    for (register int i=0;i<m;++i){
        ret=(ret+ans.a[0][i])%mod;
    }
    printf("%d\n",ret);
}

做完此题，对矩阵快速幂的理解更加深刻：

$dp[i][k]+=dp[i-1][j]$

可以看作矩阵 $base[j][k]++$

再来看最简单的斐波那契数列： $dp[i]=dp[i-1]+dp[i-2]$

我们可以这么考虑，开一个 $dp[n][2]$ 数组，列出 $dp$ 方程 $dp[i][0]+=dp[i-1][1],dp[i][1]+=dp[i-1][0],dp[i][1]+=dp[i-1][1]$ 。

于是矩阵 $base[1][0]=base[0][1]=base[1][1]=1$ 。

考虑这样的正确性， $dp$ 从上一层推到这一层，没有用到上一层之外的数。

于是可以保证这样是正确的。

其他积性函数如狄利克雷函数也可以用这样的手段优化。