你好！我是你的 OI 金牌教练。

处理 $5 \times 10^6$ 级别的数据是 NOI 竞赛中对“算法常数”与“线性思维”的终极考验。这道题的进化过程，本质上是如何利用字符串的对称性来消除重复计算的过程。

下面我将带你从最原始的思路开始，一步步推导至最先进的 $O(L)$ 算法。

第一阶段：朴素暴力 (Brute Force)

思路： 遍历每一个前缀。对于每一个长度为 $i$ 的前缀，我们从两端向中间扫描，判断其是否为回文。如果是，则根据题目定义的递推式计算阶数。

// 朴素暴力版本 - 复杂度 O(L^2)
#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool is_palindrome(const string& s, int len) {
    for (int i = 0; i < len / 2; ++i) {
        if (s[i] != s[len - 1 - i]) return false;
    }
    return true;
}

int main() {
    string s;
    cin >> s;
    int n = s.length();
    vector<int> deg(n + 1, 0);
    long long total = 0;
    for (int i = 1; i <= n; ++i) {
        if (is_palindrome(s, i)) {
            // 根据定义：阶数 = 1 + 前一半前缀的阶数
            deg[i] = deg[i / 2] + 1;
        } else {
            deg[i] = 0;
        }
        total += deg[i];
    }
    cout << total << endl;
    return 0;
}

• 时间复杂度分析：外层循环 $L$ 次，内层 is_palindrome 检查平均耗时 $O(L)$。总复杂度 $O(L^2)$。当 $L=5 \times 10^6$ 时，计算量高达 $10^{13}$，必死无疑。
• 空间复杂度分析：$O(L)$，存储阶数数组。

第二阶段：最优复杂度 - 滚动哈希优化 (Optimal Hashing)

思路升级： 判断前缀 $S[0 \dots i]$ 是否回文，核心在于判断：“正着读”是否等于“倒着读”。 通过维护两个哈希值（正向哈希和反向哈希），我们可以实现在线性扫描的过程中，$O(1)$ 判断当前前缀是否回文。

#include <cstdio>
#include <cstring>

using namespace std;

// 5*10^6 需要开全局数组，避免栈溢出
const int MAXN = 5000005;
char s[MAXN];
int deg[MAXN];

/**
 * 优化思路：
 * 1. 增量式计算哈希：
 *    正向哈希 (从左往右计算前缀): H_f = H_f * B + s[i]
 *    反向哈希 (将前缀倒序看): H_b = H_b + s[i] * B^i
 * 2. 状态转移：当前前缀若是回文，阶数直接从 dp[len/2] 转移。
 */

int main() {
    // 技巧：使用 scanf 处理大规模字符读取
    if (scanf("%s", s + 1) == EOF) return 0;
    int n = strlen(s + 1);

    unsigned long long h_f = 0, h_b = 0, p_pow = 1;
    const unsigned long long base = 131; // 进制底数，常用 131 或 13331
    long long total_ans = 0;

    for (int i = 1; i <= n; ++i) {
        // --- 关键点 1：增量更新哈希 ---
        // 正向哈希更新：原有值整体左移一位，加上新字符
        h_f = h_f * base + (unsigned long long)s[i];
        
        // 反向哈希更新：新字符作为当前最高位（权重为 base^i）加到原有值上
        h_b = h_b + (unsigned long long)s[i] * p_pow;
        p_pow *= base;

        // --- 关键点 2：O(1) 回文判定 ---
        if (h_f == h_b) {
            // 如果前缀 s[1...i] 是回文，阶数 = 1 + 长度为 i/2 的前缀阶数
            // i >> 1 即 floor(i/2)
            deg[i] = deg[i >> 1] + 1;
        } else {
            deg[i] = 0; // 不是回文，阶数为 0
        }
        
        // --- 关键点 3：结果累加 ---
        total_ans += deg[i];
    }

    printf("%lld\n", total_ans); // 注意 5e6 规模下结果必须用 long long
    return 0;
}

复杂度分析思考过程：

1. 时间复杂度：$O(L)$。
   • 我们只遍历了一次字符串。
   • 每次操作（计算哈希、查表、累加）都是常数级的 $O(1)$。
   • 对于 $5 \times 10^6$ 的数据，处理时间约为 0.1s - 0.3s，非常稳健。
2. 空间复杂度：$O(L)$。
   • deg 数组：$5 \times 10^6 \times 4$ 字节 $\approx 20$ MB。
   • s 数组：$5 \times 10^6 \times 1$ 字节 $\approx 5$ MB。
   • 总计约 $25$ MB，远低于题目给出的 256MB。

三、 时间复杂度优化建议 (进阶)

虽然 $O(L)$ 已经是理论最优，但在 NOI 竞赛中，“卡常”是常态。针对此题，还有以下优化方向：

1. 快速输入输出 (Fast I/O)：
   • scanf 在处理 500 万字符时可能耗时 0.2s 左右。可以使用 fread 批量读取，能将读取速度再提升一个数量级。
2. Manacher 算法的变体：
   • 哈希法存在极小的“哈希碰撞”概率。如果担心被出题人恶意构造数据卡哈希，可以使用 Manacher 算法。
   • Manacher 可以在 $O(L)$ 内求出以每个点为中心的最长回文半径 $R$。
   • 判断前缀 $S[1 \dots i]$ 是否回文，只需看：以位置 $(1+i)/2$ 为中心的回文半径是否覆盖了端点。
   • 代价：Manacher 代码较复杂且空间开销通常是哈希法的两倍。
3. 双哈希 (Double Hashing)：
   • 如果不放心自然溢出（unsigned long long），可以使用双模数（如 $10^9+7$ 和 $10^9+9$）同时验证。这会使速度慢一倍，但正确性几乎达到 100%。

易错点总结（金牌教练的叮嘱）

1. 哈希冲突：自然溢出哈希在 $L=5 \times 10^6$ 且数据由特殊构造时可能碰撞。底数 base 建议选取质数，且不要只选 31。
2. 下标偏移：注意题目描述中“长度为 $1$ 的阶数为 $1$”。在代码实现中，deg[1] = deg[0] + 1，因此 deg[0] 初始必须为 $0$。
3. 整型溢出：最终答案 total_ans 必须是 long long。如果是 $5 \times 10^6$ 个字符全相同（如全是 'a'），总阶数约为 $5 \times 10^6 \times \log_2(5 \times 10^6)$，远超 int 范围。

这道题是 “增量哈希” 与 “线性递推” 结合的典范。掌握了这种“通过前缀哈希 $O(1)$ 判断回文”的技巧，你就能解决大部分基础回文类题目。加油！

你好！我是你的 OI 金牌教练。

针对 Palindrome Degree (CF 7D)，我们要构造一套能够有效区分 $O(N^2)$（暴力回文检查）、$O(N \log N)$（带 Log 的字符串算法）和 $O(N)$（哈希/Manacher）的数据集。

数据规模设计

为了满足你提到的“数据文件尽可能小（约 1MB）”的要求，我将最大字符串长度设定为 $10^6$。

• 1MB 的考量：$10^6$ 个字符在文本文件中正好约为 1MB。
• 区分度：在 $N=10^6$ 时，$O(N \log N)$ 的算法会运行得比较吃力，而 $O(N^2)$ 绝对无法通过（计算量达 $10^{12}$）。

数据生成器代码 (C++14)

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <random>
#include <chrono>
#include <algorithm>

using namespace std;

// 使用 mt19937 产生高质量随机数
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// --- 核心解法：用于产生标准输出 .out ---
long long get_ans(const string& s) {
    int n = s.length();
    if (n == 0) return 0;
    vector<int> dp(n, 0);
    unsigned long long h1 = 0, h2 = 0, p_pow = 1;
    const unsigned long long seed = 131;
    long long total = 0;

    for (int i = 0; i < n; ++i) {
        h1 = h1 * seed + (unsigned long long)s[i];
        h2 = h2 + (unsigned long long)s[i] * p_pow;
        p_pow *= seed;

        if (h1 == h2) {
            // dp[i] = 1 + dp[ (i+1)/2 - 1 ]
            int prev_idx = (i + 1) / 2 - 1;
            dp[i] = (prev_idx >= 0 ? dp[prev_idx] : 0) + 1;
        } else {
            dp[i] = 0;
        }
        total += dp[i];
    }
    return total;
}

// --- 字符串生成工具 ---
string gen_random(int len) {
    string res = "";
    string charset = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    for (int i = 0; i < len; ++i) res += charset[rng() % charset.size()];
    return res;
}

string gen_all_same(int len, char c) {
    return string(len, c);
}

// 递归构造高度对称的回文串（如：S = S' + mid + S'）
string gen_recursive_palin(int target_len) {
    if (target_len <= 1) return string(1, 'a' + (rng() % 26));
    string half = gen_recursive_palin(target_len / 2);
    char mid = 'a' + (rng() % 26);
    if (target_len % 2 == 0) return half + half;
    return half + mid + half;
}

void make_test(int id, string content) {
    string in_file = to_string(id) + ".in";
    string out_file = to_string(id) + ".out";
    
    ofstream fout(in_file);
    fout << content << endl;
    fout.close();

    long long ans = get_ans(content);
    ofstream fans(out_file);
    fans << ans << endl;
    fans.close();
    
    cout << "Test Case " << id << " [N=" << content.length() << "] generated." << endl;
}

int main() {
    // 1. 样例
    make_test(1, "abacaba");

    // 2. 最小边界
    make_test(2, "z");

    // 3. 全相同字符 (阶数最高的情况)
    make_test(3, gen_all_same(1000, 'a'));

    // 4. 只有长度 1 是回文 (无回文性质)
    make_test(4, "abcdefghijklmnopqrstuvwxyz");

    // 5. 循环交替 (ababab...)
    string c5 = "";
    for(int i=0; i<5000; ++i) c5 += (i % 2 == 0 ? 'a' : 'b');
    make_test(5, c5);

    // 6. 中等随机规模
    make_test(6, gen_random(50000));

    // 7. 大规模随机 (约 1MB)
    make_test(7, gen_random(1000000));

    // 8. 深度递归回文 (阶数极大化)
    // 注意：1000000 长度的递归构造需要非递归防止爆栈，这里用迭代模拟
    string c8 = "a";
    while(c8.length() < 500000) {
        c8 = c8 + (char)('a' + rng()%26) + c8;
    }
    if(c8.length() > 1000000) c8 = c8.substr(0, 1000000);
    make_test(8, c8);

    // 9. 混合极端数据 (大量的 'a' 后面跟一个 'b')
    string c9 = gen_all_same(500000, 'a') + "b" + gen_all_same(499999, 'a');
    make_test(9, c9);

    // 10. 最大规模 (1,000,000 字符)
    make_test(10, gen_random(1000000));

    return 0;
}

数据说明 (NOI 竞赛格式)

教练的最后提示

1. 文件大小控制： 由于每个字符占 1 字节，设定 $L=10^6$ 时，.in 文件大小约为 0.95 MiB，完全符合你“1MB 以内”的要求。同时，$10^6$ 的数据量足以让任何 $O(N^2)$ 的算法跑上数小时。

2. 生成效率与内存：

   • 生成器在内部模拟了 get_ans 逻辑，时间复杂度为 $O(L)$。
   • 针对测试点 8，我使用了倍增迭代（c8 = c8 + mid + c8）代替递归，避免了函数调用深度的限制。
   • 总生成时间应在 1s 以内。

3. 读题关键点总结 (关键词)：

   • “All prefixes”：提示这是一个增量过程。
   • “$\lfloor n/2 \rfloor$”：明确指出了状态转移的方向。
   • “Sum of degrees”：说明结果可能超过 int（$10^6$ 长度阶数最高可达 $\approx \log N$，总和可能达到 $10^7$ 甚至更高，虽然 int 理论上能存，但在 NOI 中建议习惯性使用 long long 存储总和）。

加油，这套数据可以帮你完美测试出选手的算法功底！