Submission #1162033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162033		Ludissey	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	2400 ms	34320 KiB

palindromic

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;

const int p=2;
const int MOD=1e9+7;
vector<int> hsh;
vector<int> ppow;
vector<int> dpow;

int fast_pow(int x, int p){
    if(p==0) return 1;
    if(p==1) return x;
    if(p%2==0){
        int r=fast_pow(x,p/2);
        return (r*r)%MOD;
    }else{
        int r=fast_pow(x,p-1);
        return (r*x)%MOD;
    }
}

int getHASH(int l, int r){
    int ret=hsh[r]%MOD;
    if(l>0) ret=hsh[r]-hsh[l-1]+MOD;
    ret=(ret*dpow[l])%MOD;
    return ret;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int t; cin >> t;
    while(t--){
        string s; cin >> s;
        int n=sz(s);
        hsh.clear(); ppow.clear(); dpow.clear();
        hsh.resize(n); ppow.resize(n); dpow.resize(n);
        int cp=1;
        for (int i = 0; i < n; i++)
        {
            hsh[i]=(((int)s[i]-(int)'a')*cp)%MOD;
            if(i>0) hsh[i]=(hsh[i]+hsh[i-1])%MOD;
            ppow[i]=cp%MOD;
            dpow[i]=fast_pow(cp,MOD-2);
            cp=(cp*p)%MOD;
        }
        int sm=1;
        int lstI=0;
        int i=0;
        while(i<n/2){
            if(getHASH(lstI,i)==getHASH((n-1)-i,(n-1)-lstI)){
                if(i+1==(n+1)/2) sm+=1;
                else sm+=2;
                lstI=i+1;
            }
            i++;
        }
        cout << sm << "\n";
    }
    return 0;
}
// 5-0-

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