Submission #924932

#	Time	Username	Problem	Language	Result	Execution time	Memory
924932		sleepntsheep	Palindromic Partitions (CEOI17_palindromic)	C++17	0 / 100	0 ms	344 KiB

palindromic

#include <bits/stdc++.h>

#define N 200005
#define ALL(x) begin(x), end(x)
using namespace std;

#define int long long

constexpr long long B { 103 }, M { 1000000007 };


int docase()
{
    string s;
    cin >> s;
    int n = s.size(), z {};
    s = "0" + s;
    vector<int> h(2*n+2, 0), pw(2*n+2, 1), ipw(2*n+2, 1);

    auto bpow = [&](auto &&bpow, long long a, long long b) -> long long {
        if (!b) return 1;
        auto r = bpow(bpow, a, b>>1);
        if (b&1) return r*r%M*a%M;
        return r*r%M;
    };
    for (auto &c : s) c -= 'a';

    for (int i = 1; i <= n; ++i)
        pw[i] = 1ll * pw[i-1] * B % M, ipw[i] = bpow(bpow, pw[i], M-2);

    for (int i = 1; i <= n; ++i)
        h[i] = (h[i-1] + ((long long)s[i] * pw[i] % M)) % M;


    auto sub = [&](int l, int r){
        auto base = (h[r] - h[l-1] + M) % M;
        (base *= ipw[l]) %= M;
        return base;
    };

    for (int f, i = 1, j; i <= n/2;)
    {
        f = 0;
        for (j = i; j <= n/2; ++j)
        {
            if (sub(i, j) == sub(n-j+1, n-i+1))
            {
                z += 2;
                f = 1;
                break;
            }
        }
        if (!f) ++z;
        i = j + 1;
        if (i > n / 2 and f) ++z;
    }

    cout << z << '\n';

    return 0;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int T;
    cin >> T;
    while (T--) docase();
    return 0;
}

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