首页 > 代码库 > CodeForces 7D Palindrome Degree
CodeForces 7D Palindrome Degree
字符串hash。首先说下需要注意的地方:当对Mod取余时,可能造成本不相同的,取余结束之后相同了。
此时应对多个不同的Mod取余,多次计算只能说降低上述情况的发生。感觉正式比赛中不会有这种题,比较拼RP。
比如此题,Mod = 2^32,可以,Mod = 2^64,WA了。。。
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <cmath> #include <stack> #include <map> #include <ctime> #include <iomanip> #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-6) #define LL long long #define ULL unsigned long long #define _LL __int64 #define INF 0x3f3f3f3f #define Mod 1000000007 using namespace std; const int MAXN = 5000010; char s[MAXN]; ULL e = 256; ULL pre[MAXN],suf[MAXN]; ULL p1[MAXN],s1[MAXN]; LL K[MAXN]; int main() { scanf("%s",s+1); int i,n = strlen(s+1); for(i = 1,pre[0] = 0;i <= n; ++i) pre[i] = pre[i-1]*e + s[i]; for(i = 2,suf[1] = s[1];i <= n; ++i) suf[i] = suf[i-1] + s[i]*e,e *= 256; e = 256; for(i = 1,p1[0] = 0;i <= n; ++i) { p1[i] = p1[i-1]*e + s[i]; p1[i] %= Mod; } for(i = 2,s1[1] = s[1];i <= n; ++i) { s1[i] = s1[i-1] + s[i]*e,e *= 256; e %= Mod,s1[i] %= Mod; } K[0] = 0; for(K[0] = 0,i = 1;i <= n; ++i) { if(pre[i] == suf[i] && p1[i] == s1[i]) K[i] = K[i/2] + 1; else K[i] = 0; } LL ans = 0; for(i = 1;i <= n; ++i) ans += K[i]; printf("%I64d\n",ans); return 0; }
CodeForces 7D Palindrome Degree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。