3.4知识精炼（三）高清版本.pdf

知识精炼（三）

主讲人：邓哲也

BZOJ1009GT考试

给定数字串A[1..m]

构造一个数字串X[1..n]，使得串中不出现数字串A

求出方案数模k的结果

9

n≤10，m≤20，k≤1000

样例输入：

43100

111

答案：81

BZOJ1009GT考试

用f[i][j]来表示目前构造出的串是X[1..i]，匹配到A

的第j个字符。

枚举第j+1个数填k

如果k正好是A[j+1]，那么就会转移到f[i+1][j+1]

否则会转移到哪呢？

沿着fail[j],fail[fail[j]]…一直往回走，直到

A[fail[j]+1]=k

会转移到f[i+1][fail[j]+1]

BZOJ1009GT考试

可以发现f[i]到f[i+1]的转移可以看做左乘一个转移矩

阵。

我们只要算出这个矩阵的n次幂，再乘上f[0]就能得到

我们想要的f[n]了。

3

时间复杂度O(mlogn)

BZOJ1009GT考试

voidmul(inta[27][27],intb[27][27],intans[27][27]){

inttmp[27][27];

for(inti=0;im;++i){

for(intj=0;jm;++j){

tmp[i][j]=0;

for(intk=0;km;++k){

tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%

mod;

}

}

}

for(inti=0;im;++i){

for(intj=0;jm;++j){

ans[i][j]=tmp[i][j];

}

}

}

BZOJ1009GT考试

intmain(){

scanf(%d%d%d,n,m,mod);

scanf(%s,ch+1);

p[1]=1,p[2]=1;

for(inti=2;im;++i){

intj=p[i];

while(j1ch[j]!=ch[i])j=p[j];

p[i+1]=(ch[i]==ch[j]?j+1:1);

}

BZOJ1009GT考试

for(inti=0;im;++i){

for(intj=0;j=9;++j){

intt=i+1;

while(t1ch[t]-0!=j)t=p[t];

if(ch[t]-0!=j)t--;

if(t!=m)b[t][i]=(b[t][i]+1)%mod;

}

}

BZOJ1009GT考试

for(inti=0;im;++i){

a[i][i]=1;

}

while(n){

if(n1)mul(a