做网站的框架模版,html做静态网站,南昌加盟网站制作,网站集约化建设的优点正题
题目链接:https://www.luogu.com.cn/problem/P3193 题目大意
求有多少个长度为nnn的字符串不包含子串sss。 解题思路
考虑dpdpdp#xff0c;用fi,jf_{i,j}fi,j表示第iii个已经匹配到jjj时的方案数。
显然这与正常匹配十分相似#xff0c;我们分为两种情况 ansi1sj…正题
题目链接:https://www.luogu.com.cn/problem/P3193 题目大意
求有多少个长度为nnn的字符串不包含子串sss。 解题思路
考虑dpdpdp用fi,jf_{i,j}fi,j表示第iii个已经匹配到jjj时的方案数。
显然这与正常匹配十分相似我们分为两种情况
ansi1sj1ans_{i1}s_{j1}ansi1sj1那么转移到fi1,j1f_{i1,j1}fi1,j1ansi1!sj1ans_{i1}!s_{j1}ansi1!sj1此时我们不能直接转移到fi1,0f_{i1,0}fi1,0因为有可能sss的某段前缀和ansansans的这段后缀相等考虑KMPKMPKMP。我们用KMPKMPKMP处理出nextnextnext数组然后往前跳到一个匹配的位置kkk那么就可以转移到fi1,k1f_{i1,k1}fi1,k1。
此时我们就有了一个O(nm2)O(nm^2)O(nm2)的做法时间复杂度承担不下我们可以发现每一次fff的转移方程都是相同的所以我们用矩阵乘法优化就好了。
时间复杂度O(m3logn)O(m^3\log n)O(m3logn) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int Size25;
struct Matrix{int a[Size][Size];
}f;
int n,m,XJQ,ans,next[Size];
char s[Size];
Matrix operator*(Matrix a,Matrix b){Matrix c;memset(c.a,0,sizeof(c.a));for(int i0;im;i)for(int j0;jm;j)for(int k0;km;k)(c.a[i][j]a.a[i][k]*b.a[k][j]%XJQ)%XJQ;return c;
}
void KMP()
{next[0]-1;next[1]0;for(int i2,j0;im;i){while(js[i]!s[j1]) jnext[j];j(s[i]s[j1]);next[i]j;}return;
}
Matrix power(Matrix x,int b)
{Matrix ansx;b--;while(b){if(b1) ansans*x;xx*x;b1;}return ans;
}
int main()
{scanf(%d%d%d,n,m,XJQ);scanf(%s,s1);KMP();for(int i0;im;i)for(int j0;j10;j){int ui;while(u(j0)!s[u1]) unext[u];u(s[u1](j0));if(um) continue;f.a[i][u];}fpower(f,n);for(int i0;im;i)ans(ansf.a[0][i])%XJQ;printf(%d,ans);
}
