原题链接

题目大意

称长度为$n$的字符串是$k$阶回文，如果这个字符串的长度为一半(下取整)的前缀和后缀都是$k-1$阶回文
定义空串是$0$阶回文
问字符串所有前缀的回文阶数之和

解题思路

不知道为什么这题能是$2200$分的题
可能本来是想考察$Manacher$
于是字符串哈希又水了一发
前缀哈希加后缀哈希判回文，就没什么了

具体代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
typedef long long LL;
typedef unsigned long long ULL;
typedef std::pair<int, int> PII;
const LL N = 5e6 + 10;
const LL M = 50;
const LL INF = 0x7f7f7f7f7f7f7f7f;
const LL MOD = 1e9 + 7;
const LL P = 131;
LL n, m, q;
LL a[N];
ULL fh[N], bh[N], base[N];
std::string str;
LL ans;
LL dp[N];
ULL getfh(int l, int r)
{
    return fh[r] - fh[l - 1] * base[r - l + 1];
}
ULL getbh(int l, int r)
{
    return bh[r] - bh[l - 1] * base[r - l + 1];
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    // std::cin >> T;
    while (T--)
    {
        std::cin >> str;
        n = str.size();
        str = "?" + str;
        base[0] = 1;
        for (int i = 1; i <= n; ++i)
            base[i] = base[i - 1] * P;
        for (int i = 1; i <= n; ++i)
        {
            fh[i] = fh[i - 1] * P + str[i];
            bh[i] = bh[i - 1] * P + str[n - i + 1];
        }
        for (int i = 1; i <= n; ++i)
        {
            if (getfh(1, i / 2) == getbh(n - i + 1, n - i + i / 2))
            {
                dp[i] = dp[i / 2] + 1;
                ans += dp[i];
            }
        }
        std::cout << ans << '\n';
    }
    return 0;
}

Codeforces杂题