Cod sursa(job #1979994)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 11 mai 2017 21:11:11
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
# include <cstdio>
# include <cstdlib>

using namespace std;

const int MAX_N = 2000005;
char s[MAX_N];

const int MOD = 1000000007;
const long long sigma = 31;
int spow[MAX_N];
int hl[MAX_N], hr[MAX_N];


int main() {
    FILE *fin = fopen( "pscpld.in", "r" ), *fout = fopen( "pscpld.out", "w" );

    int n = 1;
    char ch = fgetc( fin );
    while ( ch != '\n' ) {
        s[n ++] = 'z' + 1;
        s[n ++] = ch;
        ch = fgetc( fin );
    }
    s[n ++] = 'z' + 1;

    spow[0] = 1;
    for ( int i = 1; i <= n; i ++ )
        spow[i] = spow[i - 1] * sigma % MOD;
    for ( int i = 1; i < n; i ++ )
        hl[i] = ( hl[i - 1] + spow[i - 1] * ( s[i] - 'a' + 1LL ) ) % MOD;
    for ( int i = n - 1; i > 0; i -- )
        hr[i] = ( hr[i + 1] + spow[n - i - 1] * ( s[i] - 'a' + 1LL ) ) % MOD;

    long long k = 0;

    for ( int i = 1; i < n; i ++ ) {
        int t = 0;
        for ( int pas = ( 1 << 21 ); pas > 0; pas >>= 1 )
            if ( i - t - pas >= 0 && i + t + pas <= n &&
               ( long long ) ( ( hl[i] - hl[i - t - pas] + MOD ) % MOD ) * spow[n - (i - t - pas)] % MOD ==
               ( long long ) ( ( hr[i] - hr[i + t + pas] + MOD ) % MOD ) * spow[i + t + pas] % MOD )
                t += pas;
        k += t / 2;
    }

    fprintf( fout, "%lld", k );

    fclose( fin );
    fclose( fout );

    return 0;
}