结衣波多野下载,打印机清零软件下载,异形契约中国上映
给出一个字符串,定义$num[i]$表示在$[1, i]$区间内互不重复的相同前后缀的数量。
最终输出$\prod_{i = 1}^n (num[i] + 1)$
去年这个时候做的题今年还是做不出来
不难看出这题应该要魔改KMP
比较烦的一个地方是要求互不重叠,我们可以先考虑求出有重叠的情况。
如果对KMP理解的比较透彻的话不难看出$num$数组是可以递推的。
具体来说是这样的(图片来自)
然后暴力跳到一个$j < i / 2$的位置统计答案就行了。
注意不能同时跳,会T飞。。
#include<cstdio> #include<queue> #include<cstring> #include<cstdlib> #define LL long long using namespace std; const int MAXN = 1e6 + 10, mod = 1e9 + 7; char s[MAXN]; LL g[MAXN]; int nxt[MAXN]; void insert(char *s) { int N = strlen(s + 1); g[1] = 1; for(int i = 2, j = 0; i <= N; i++) { while(s[i] != s[j + 1] && j) j = nxt[j]; if(s[i] == s[j + 1]) j++; g[i] += g[j] + 1; nxt[i] = j; } LL ans = 1; for(int i = 1, j = 0; i <= N; i++) { while(s[i] != s[j + 1] && j) j = nxt[j]; if(s[i] == s[j + 1]) j++; while(j > i / 2 && j) j = nxt[j]; ans = ans * 1ll * (g[j] + 1) % mod; } printf("%lld\n", ans); } int main() { int QwQ; scanf("%d", &QwQ); while(QwQ--) { memset(nxt, 0, sizeof(nxt)); memset(g, 0, sizeof(g)); scanf("%s", s + 1), insert(s); } return 0; } /* 3 011 11 */
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论