Steven_MengのBlog

传送门

我们有一个搞笑的做法:

$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$的状态里面。

1
2
3
4
5
6
7
8
9
10
11
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];

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

于是得到以下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#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$从上一层推到这一层,没有用到上一层之外的数。

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

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

 评论