Submission #867701

#	Time	Username	Problem	Language	Result	Execution time	Memory
867701		Dec0Dedd	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	98 ms	36436 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1e9+7;
const ll P = 2137;
const int N = 1e6+10;

ll p[N], h[N], inv[N];

ll bpw(ll x, ll n) {
    if (n == 0) return 1;
    ll c=bpw(x, n/2);
    (c=c*c)%=MOD;
    if (n&1) return (c*x)%MOD;
    return c;
}

ll hsh(int l, int r) {
    ll v=((h[r]-h[l-1])%MOD+MOD)%MOD;
    return (v*inv[l])%MOD;
}

void solve() {
    string s; cin>>s; h[0]=0;

    int n=s.size();
    for (int i=1; i<=n; ++i) h[i]=(h[i-1]+s[i-1]*p[i])%MOD;

    int ans=0, l=0;
    for (int i=1; i<=n/2; ++i) {
        if (hsh(l+1, i) == hsh(n-i+1, n-l)) l=i, ans+=2;
    }

    if (l < (n+1)/2) ++ans;
    cout<<ans<<"\n";
}

int main() {
    ios_base::sync_with_stdio(NULL);
    cout.tie(NULL);
    
    p[0]=1, p[1]=P;
    inv[0]=1, inv[1]=bpw(P, MOD-2);
    for (int i=2; i<N; ++i) (p[i]=p[i-1]*P)%=MOD, (inv[i]=inv[i-1]*inv[1])%=MOD;

    int t; cin>>t;
    while (t--) solve();
}

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