Cod sursa(job #2802542)

Utilizator icc577Constantinescu Iustinian Cristian icc577 Data 18 noiembrie 2021 12:42:15
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.2 kb
#include <iostream>
#include <cstdio>
#include <fstream>
using namespace std;
ifstream in ("pscpld.in");
ofstream out ("pscpld.out");
const long long M1=1000000009;
const long long M2=1000000007;
const long long M3=999996007;
typedef struct haash
{
    long long m1;
    long long m2;
    long long m3;
}haash;
haash add (haash a, haash b)
{
    haash res;
    res.m1=(a.m1+b.m1)%M1;
    res.m2=(a.m2+b.m2)%M2;
    res.m3=(a.m3+b.m3)%M3;
    return res;
}
haash subt (haash a, haash b)
{
    haash res;
    res.m1=(a.m1-b.m1+M1)%M1;
    res.m2=(a.m2-b.m2+M2)%M2;
    res.m3=(a.m3-b.m3+M3)%M3;
    return res;
}
haash mult (long long b,haash a)
{
    haash res;
    res.m1=(a.m1*b)%M1;
    res.m2=(a.m2*b)%M2;
    res.m3=(a.m3*b)%M3;
    return res;
}
haash multh (haash a, haash b)
{
    haash res;
    res.m1=(a.m1*b.m1)%M1;
    res.m2=(a.m2*b.m2)%M2;
    res.m3=(a.m3*b.m3)%M3;
    return res;
}
bool eq(haash a, haash b)
{
    return (a.m1==b.m1&&a.m2==b.m2&&a.m3==b.m3);
}
haash tw27to_2_x (int dexp)
{
    haash res;
    res.m1=res.m2=res.m3=27;
    for(int i=0; i<dexp; i++)
    {
        res=multh(res,res);
    }
    return res;
}
int main()
{

    string s;
    in>>s;
    haash fsum [1000010];///forwards  sum
    haash bsum [1000010];///backwards sum
    fsum[0].m1=fsum[0].m2=fsum[0].m3=0;
    int i;
    haash pows27;
    pows27.m1=pows27.m2=pows27.m3=1;
    for(i=0; s[i]!='\0'; i++)
    {
        fsum[i+1]=add(fsum[i],mult(s[i]-'a'+1,pows27));
        pows27=mult(27,pows27);
    }
    int length=i;
    pows27.m1=pows27.m2=pows27.m3=1;
    for(bsum[i].m1=bsum[i].m2=bsum[i].m3=0; s[i]!='\0'; i++)
    {
        bsum[i-1]=add(bsum[i],mult(s[i]-'a'+1,pows27));
        pows27=mult(27,pows27);
    }
    long long res=0;
    for(i=1; i<=length; i++)
    {
        int r=0;///impare
        for(int step=1<<19; i>0; i=i>>1)
        {
            int maybe=r+step;
            if(i-maybe-1<0||i+maybe>length)
            {
                continue;
            }
            if(i-1>length-i)
            {
                if(eq(subt(fsum[i-1],fsum[i-1-r]),multh(subt(bsum[i],bsum[i+r]),tw27to_2_x(2*i-length-1))))
                {
                    r=maybe;
                }
            }
            else
            {
                if(eq(subt(bsum[i],bsum[i+r]),multh(subt(fsum[i-1],fsum[i-1-r]),tw27to_2_x(length+1-2*i))))
                {
                    r=maybe;
                }
            }
        }
        res+=r+1;
        r=0;
        for(int step=1<<19; i>0; i=i>>1)
        {
            int maybe=r+step;
            if(i-maybe<0||i+maybe>length)
            {
                continue;
            }
            if(i>length-i)
            {
                if(eq(subt(fsum[i],fsum[i-r]),multh(subt(bsum[i],bsum[i+r]),tw27to_2_x(2*i-length))))
                {
                    r=maybe;
                }
            }
            else
            {
                if(eq(subt(bsum[i],bsum[i+r]),multh(subt(fsum[i],fsum[i-r]),tw27to_2_x(length-2*i))))
                {
                    r=maybe;
                }
            }
        }
        res+=r;
    }
    out<<res;
    return 0;
}