2018 ICPC 南京网络赛 skr
程序员文章站
2022-06-04 12:21:42
...
题意:
给出一个字符串,求它的所有回文子串转化成数字的和,对1e9+7取模。
题解:
先上Manacher,然后枚举每个点,按照半径从大到小的顺序枚举回文串,遇到出现过的就break,统计答案即可。
注意的是,判重时只能用pb_ds中的gp_hash_table,unordered_map会T,同时需要两个字符串hash关键子,一个会WA。
Manacher+暴力枚举回文串+pb_ds的hash_talbe判重+2个关键字的字符串hash。
代码:
#include<bits/stdc++.h>
#include<hash_map>
#define N 2000010
#define INF 0x3f3f3f3f
#define eps 1e-10
#define pi 3.141592653589793
#define LL long long
#define pb push_back
#define cl clear
#define si size
#define lb lowwer_bound
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define P 1000000007
#define mod 998244353
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
char s[N],ss[N<<1];
int H[N],A[N],r[N<<1],p[N],pp[N],len;
gp_hash_table<LL,bool>mp;
int Init()
{
int len = strlen(s+1);
ss[0] = '$';ss[1] = '#';
int j = 2;
for (int i = 1; i <= len; i++)ss[j++] = s[i],ss[j++] = '#';
ss[j] = '\0';
return j;
}
void Manacher()
{
len=Init();
int p,mx=0;
for (int i = 1; i < len; i++)
{
if (i<mx) r[i]=min(r[2*p-i],mx-i);else r[i] = 1;
while (ss[i-r[i]]==ss[i+r[i]]) r[i]++;
if (mx<i+r[i])p=i,mx=i+r[i];
}
}
inline int cal(int x,int y)
{
return (H[y]-(LL)H[x-1]*p[y-x+1]%mod+mod)%mod;
}
inline int call(int x,int y)
{
return (A[y]-(LL)A[x-1]*pp[y-x+1]%P+P)%P;
}
int main()
{
while(~scanf("%s",s+1))
{
int n=strlen(s+1); p[0]=1;pp[0]=1;
for (int i=1;i<=n;i++) A[i]=((LL)A[i-1]*10+(s[i]-'0'))%P,H[i]=((LL)H[i-1]*377+s[i])%mod,
p[i]=(LL)p[i-1]*377%mod,pp[i]=(LL)pp[i-1]*10%P;
Manacher();
int ans=0;mp.clear();
for (int i=2;ss[i];i++)
{
if (ss[i]=='#' && r[i]==1) continue;
int x=i/2-r[i]/2+1,y=i/2+r[i]/2-!(i&1);
while(x<=y)
{
LL t=cal(x,y),tt=call(x,y);
if (mp[(t<<31)|tt]) break;
ans=(ans+tt)%P;
mp[(t<<31)|tt]=1;
x++;y--;
}
}
printf("%d\n",ans);
}
}
上一篇: How to fix wicd 1.7.0+ds1-5 Connection Failed: Bad Password on Ubuntu 10.10 (Mav
下一篇: 如何安装系统认证签名过的APK
推荐阅读
-
2017 ICPC网络赛(西安)--- Xor
-
【计蒜客】2018ICPC徐州赛区网络赛H Ryuji doesn't want to study(树状数组)
-
ACM-ICPC 2018 徐州赛区网络预赛 H - Ryuji doesn't want to study
-
ACM-ICPC 2018 徐州赛区网络预赛 H. Ryuji doesn't want to study(线段树区间求和)
-
ACM-ICPC 2018 徐州赛区网络预赛 H. Ryuji doesn't want to study—— 树状数组
-
ACM-ICPC 2018 徐州赛区网络预赛 H Ryuji doesn't want to study(线段树 两种做法)
-
【ACM-ICPC 2018 徐州赛区网络预赛】H题 Features Track ---- 树状数组
-
ICPC网络赛 Ryuji doesn't want to study (线段树/树状数组)
-
ACM-ICPC 2018 徐州赛区网络预赛 G. Trace (线段树维护)
-
计蒜客 Trace(2018 ICPC亚洲区域赛网络赛 徐州 G)(线段树)