Submission #340439

#	Time	Username	Problem	Language	Result	Execution time	Memory
340439		blue	Palindromic Partitions (CEOI17_palindromic)	C++11	0 / 100	1 ms	492 KiB

palindromic

#include <iostream>
#include <string>
using namespace std;

//a^p-1 = 1 mod p
//a^p-2 = 1/a mod p

long long p[31];
long long mod = 1e9 + 7;

long long prefhash[31];

long long pow(long long base, long long exp)
{
    if(exp == 0) return 1;
    if(exp % 2) return (pow(base, exp-1) * base) % mod;
    long long temp = pow(base, exp/2);
    return (temp * temp) % mod;
}

long long gethash(long long a, long long b)
{
    return (mod + prefhash[b] - (prefhash[a-1]*p[b-(a-1)]) % mod) % mod;
}

void run()
{
    string S;
    cin >> S;
    long long n = S.length();
    S = " " + S;

    prefhash[0] = 0;
    for(long long i = 1; i <= n; i++) prefhash[i] = (p[1] * prefhash[i-1]  +  (S[i] - 'a' + 1)) % mod;

    long long res = 0;
    long long j = 1;
    for(long long i = 1; 1; i++)
    {
        // cout << j << ' ' << i << ' ' << n-i+1 << ' ' << n-j+1 << '\n';
        // cout << gethash(j, i) << ' ' << gethash(n-i+1, n-j+1) << '\n';
        if(gethash(j, i) == gethash(n-i+1, n-j+1))
        {
            if(i == n-j+1)
            {
                res += 1;
                break;
            }
            else
            {
                res += 2;
            }
            j = i+1;
        }
    }
    cout << res << '\n';
}

int main()
{
    p[0] = 1;
    for(long long i = 1; i <= 30; i++) p[i] = (p[i-1] * 347) % mod;

    long long t;
    cin >> t;
    for(long long i = 1; i <= t; i++) run();
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40