之前学矩阵乘的时候做的题,当时因为不会\(kmp\)搜索一稀里糊涂过去了,现在填个坑。
头图
是\(Logos\)!
P3193 [HNOI2008] GT考试
题链:洛谷 题库
题目大意:
求有多少个长度为\(n\)的数字串的子串中不包含给出的长度为\(m\)位的串,范围 \(n <= 1e9\),$ m <= 20$。
思路:
首先考虑DP,令\(zl[i][j]\)为原串匹配到第\(i\)位,短串最多可以匹配到第\(j\)位的方案数。
那么显然答案为:
状态转移方程为:
其中的\(p\)不一定是\(0\)或者\(j-1\),因为加入字符\(k\)后,会有三种情况产生:
- 与原串中的下一个字符匹配;
- 失配,无法与任何字符相匹配;
- 重新与原串的另一个前缀匹配。
那么上面的式子就无法支持我们完成之后的操作了,所以我们换一种写法。
令\(dh[k][j]\)为一个匹配了长度为\(k\)的串,有多少种增加数字的方法,使得与原串匹配的长度变成\(j\)。
状态转移方程为:
由于我们知道原串,所以整个\(dh\)数组是固定的,我们可以预处理出这个数组。方法是用\(kmp\)求出\(next\)数组后,枚举匹配长度\(k\)和字符\(ch\),暴力计算出能匹配到前缀的长度。
那么,由于这道题是矩阵乘法专题里的\(dh\)数组恒不变,显然能想到用矩阵乘法的相关知识来解决。
因为我们最后只需要第\(n\)行矩阵,所以我们把每一行\(zl[i][j]\)抽象成一行,\(m-1\)列的矩阵\(hdl[i]\),可推导出\(hdl[i]=hdl[i-1]*yns\),那么,\(hdl[n]=hdl[0]*yns^n\)。
用矩阵快速幂求出\(yns^n\),再用矩阵乘法使其与\(hdl\)相乘,即可得出最终矩阵,再把答案一加一模就ok啦。
code:
#include<bits/stdc++.h>
#define fo(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
typedef long long ll;
namespace Aventurine
{inline int qr(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}inline void qw(int x){if(!x)return;qw(x/10);putchar(x%10+'0');}inline void qkg(int x){if(x==0)putchar('0');elseqw(x);putchar(' ');}inline void qhh(int x){if(x==0)putchar('0');elseqw(x);putchar('\n');}
}
#define qr qr()
using namespace std;
using namespace Aventurine;
const int Ratio=0;
const int N=55;
const int maxi=INT_MAX;
int n,len,mod,ans;
int kmp[N];
char s[N];
struct rmm
{int a[N][N];rmm(){//一定要初始化!一定要初始化!一定要初始化! memset(a,0,sizeof a);}//在结构体中定义的数组需要初始化!
}yns,hdl;
rmm operator*(rmm a,rmm b)//矩阵乘
{rmm c;fo(i,0,len-1)fo(j,0,len-1)fo(k,0,len-1)c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%mod+mod)%mod;return c;
}
rmm operator^(rmm a,int t)//矩阵快速幂
{rmm b;fo(i,0,len-1)b.a[i][i]=1;while(t){if(t&1)b=b*a;a=a*a;t>>=1;}return b;
}
namespace Wisadel
{void Wprekmp()//kmp初始化{int j=0;fo(i,2,len){while(j&&s[j+1]!=s[i])j=kmp[j];if(s[j+1]==s[i])j++;kmp[i]=j;}}void Wwork(){fo(i,0,len-1)for(char ch='0';ch<='9';ch++){//枚举添加的字符 int j=i;while(j&&s[j+1]!=ch)j=kmp[j];if(s[j+1]==ch)j++;yns.a[i][j]=(yns.a[i][j]+1)%mod;}hdl.a[0][0]=1;//即为hdl[0] yns=yns^n;hdl=hdl*yns;fo(i,0,len-1)ans=(ans+hdl.a[0][i])%mod;}short main(){n=qr,len=qr,mod=qr;scanf("%s",s+1);Wprekmp();Wwork();printf("%d\n",ans);return Ratio;}
}
int main(){return Wisadel::main();}
完结撒花
我放两张。
谁有W的好图啊aa球球了QwQ