这是一个值得庆祝的时刻!
BZOJ rank终于进2000辣!
另外这道题的题号还是我的生日!
这道题还是挺难的
首先我们可以想出一种dp的思路
用f[i][j]表示到前i位匹配到不jiry串第j位的方案数
那么转移就是枚举下一位c,假设加上了这个c之后匹配到第k位,那么f[i+1][k]+=f[i][j]。
f[0][0]=1,f[0][j]=0(j≠0)
特判i为m时强制只能转移到m。
判断加上c后到匹配第几位可以用KMP预处理。
考虑优化,可以发现转移和i无关,那么用a[j][k]表示匹配到第j位能够转移到匹配到第k位的数字c的取值数
那么用单位矩阵*a矩阵的n次方,也就是a矩阵自乘n次,答案即为
$$\sum_{i=0}^{m-1}a[0][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 |
// <1009.cpp> - 05/20/16 18:13:22 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0;char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return res; } int g1(){ char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); return ch-'0'; } const int MAXN=30; const int INF=1e9; int m,MOD; int s[MAXN],next[MAXN]; struct matrix{ int a[MAXN][MAXN]; matrix(){memset(a,0,sizeof(a));} int* operator [](int x){return a[x];} matrix operator *(matrix b){ matrix ans; for(int i=0;i<m;i++) for(int j=0;j<m;j++) for(int k=0;k<m;k++)(ans[i][j]+=a[i][k]*b[k][j])%=MOD; return ans; } }a; int main(){ int n=gi();m=gi();MOD=gi(); for(int i=1;i<=m;i++)s[i]=g1(); int o=0; for(int i=2;i<=m;i++){ while(o&&s[i]!=s[o+1])o=next[o]; if(s[i]==s[o+1])o++; next[i]=o; } for(int i=0;i<m;i++) for(int now=0;now<10;now++){ int o=i; while(o&&now!=s[o+1])o=next[o]; a[i][o+(now==s[o+1])]++; } matrix ans;ans[0][0]=1; while(n){ if(n&1)ans=ans*a; a=a*a; n>>=1; } int ANS=0; for(int i=0;i<m;i++)ANS=(ANS+ans[0][i])%MOD; printf("%d",ANS); return 0; } |