Cod sursa(job #3272648)

Utilizator tudor_costinCostin Tudor tudor_costin Data 30 ianuarie 2025 17:34:59
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <bits/stdc++.h>

using namespace std;
#define int long long
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int base=31,mod=1e9+7,Nmax=1e6+5;
int pw[Nmax],inv_pw[Nmax];
int hsh[Nmax],rev[Nmax];
int n;
int power(int a,int b)
{
    int sol=1;
    while(b)
    {
        if(b%2==1) sol=sol*a%mod;
        a=a*a%mod;
        b=b/2;
    }
    return sol;
}
void init()
{
    pw[0]=1;
    inv_pw[0]=1;
    for(int i=1;i<=n;i++)
    {
        pw[i]=pw[i-1]*base%mod;
        ///cout<<i<<' '<<pw[i]<<'\n';
        inv_pw[i]=inv_pw[i-1]*power(base,mod-2)%mod;
    }
}
int calch(int l,int r)
{
    if(l>r) return 0;
    return (hsh[r]+mod-hsh[l-1])%mod*inv_pw[l]%mod;
}
int calcr(int l,int r)
{
    if(l>r) return 0;
    return (rev[l]+mod-rev[r+1])%mod*inv_pw[n-r-1]%mod;
}
signed main()
{
    string s;
    fin>>s;
    n=s.size();
    init();
    for(int i=0;i<n;i++)
    {
        if(i>0) hsh[i]=(hsh[i-1]+pw[i]*(s[i]-'a'+1)%mod)%mod;
        else hsh[i]=s[i]-'a'+1;
    }
    for(int i=n-1;i>=0;i--)
    {
        rev[i]=(rev[i+1]+pw[n-i-1]*(s[i]-'a'+1)%mod)%mod;
        ///cout<<i<<' '<<rev[i]<<'\n';
    }
    int sol=0;
    for(int i=0;i<n;i++)
    {
        ///impare
        int l=0,r=min(i,n-i-1);
        int len=0;
        while(l<=r)
        {
            int mid=(l+r)/2;
            int sumr=calch(i+1,i+mid);
            int suml=calcr(i-mid,i-1);
            ///cout<<l<<' '<<r<<' '<<i<<' '<<mid<<' '<<sumr<<' '<<suml<<'\n';
            if(sumr==suml)
            {
                len=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        ///cout<<i<<' '<<len<<'\n';
        sol+=len+1;
        ///pare
        if(i==0 || s[i]!=s[i-1]) continue;
        l=0,r=min(i-1,n-i-1);
        len=0;
        while(l<=r)
        {
            int mid=(l+r)/2;
            int sumr=calch(i+1,i+mid);
            int suml=calcr(i-1-mid,i-2);
            if(sumr==suml)
            {
                len=mid;
                l=r+1;
            }
            else r=l-1;
        }
        ///cout<<i<<' '<<len<<' '<<"pare"<<'\n';
        sol+=len+1;
    }
    fout<<sol<<'\n';
    return 0;
}