欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018 ICPC 南京网络赛 skr

程序员文章站 2022-06-04 12:21:42
...

2018 ICPC 南京网络赛 skr

2018 ICPC 南京网络赛 skr

题意:

给出一个字符串,求它的所有回文子串转化成数字的和,对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);
    }
}

 

相关标签: 南京网络赛