题解

问题分析

题目要求统计字符串 ( S ) 的所有有效拆分方案数，拆分形式为 ( S = (AB)^i C )，其中：

• ( A, B, C ) 均为非空字符串，( i \geq 1 )；
• ( F(A) \leq F(C) )，其中 ( F(X) ) 表示字符串 ( X ) 中出现奇数次的字符数量。

核心挑战是高效枚举所有可能的 ( A, B, C ) 组合，并验证拆分形式及 ( F(A) \leq F(C) ) 的条件。

核心思路

1. 拆分形式的关键特征：( (AB)^i ) 表示 ( AB ) 重复 ( i ) 次，因此 ( A ) 在每个重复单元中必须完全相同。例如，第 2 个 ( AB ) 中的 ( A ) 需与第 1 个 ( AB ) 中的 ( A ) 一致，以此类推。

2. 快速验证重复的 ( A )：利用字符串哈希预处理前缀哈希值，通过比较哈希值快速判断不同位置的 ( A ) 是否相同，避免暴力字符串比较的高耗时。

3. 奇偶状态的高效计算：用前缀异或（bitset<26>）记录每个位置前的字符奇偶出现次数（ev[i] 表示前 ( i ) 个字符的奇偶状态）。( F(X) ) 可通过异或结果的 1 的位数直接计算（即 (ev[end] ^ ev[start]).count()）。

4. 枚举与计数优化：枚举 ( A ) 的长度 ( p )，通过二分查找确定 ( A ) 最多可重复的次数 ( k )（即最大 ( i )），再利用计数数组累计 ( F(A) ) 的数量，快速统计满足 ( F(A) \leq F(C) ) 的方案数。

算法步骤

1. 预处理：

   • 前缀哈希：计算 ( h[i] ) 表示前 ( i ) 个字符的哈希值，用于快速比较子串是否相等。
   • 前缀奇偶状态：计算 ( ev[i] )（bitset<26>），表示前 ( i ) 个字符中每个字符出现次数的奇偶性（1 为奇数次，0 为偶数次）。

2. 枚举 ( A ) 的长度 ( p )：

   • 对于每个 ( p \geq 1 )（( A ) 非空），通过二分查找确定最大的 ( k )，使得 ( A )（长度 ( p )）在 ( (AB)^i ) 中可重复 ( k ) 次（即前 ( k ) 个 ( A ) 完全相同）。

3. 计算有效方案数：

   • 对于每个 ( p ) 和对应的 ( k )，分 ( i ) 为奇数和偶数两种情况（因不同 ( i ) 对应 ( C ) 的起始位置不同，( F(C) ) 可能不同）。
   • 计算 ( F(C) )（( C ) 是 ( S ) 中 ( (AB)^i ) 后的剩余部分），利用计数数组 ( c ) 累计所有 ( F(A) \leq F(C) ) 的方案数（( c[i] ) 记录当前 ( F(A) = i ) 的 ( A ) 的数量）。

4. 累加结果：将所有 ( p ) 的贡献累加，得到最终方案数。

关键细节解析

• 字符串哈希比较：通过前缀哈希值和预处理的基数幂（powB），可在 ( O(1) ) 时间内比较两个子串是否相等，确保二分查找的高效性。
• 前缀异或计算 ( F(X) )：( F(X) ) 是 ( X ) 中奇数次字符的数量，等价于 ( ev[end] \oplus ev[start] ) 中 1 的位数（异或后 1 表示该字符在 ( X ) 中出现奇数次）。
• 二分查找最大 ( k )：对于每个 ( p )，二分查找最大 ( k ) 使得前 ( k ) 个 ( A ) 完全相同，限制 ( i ) 的有效范围，减少无效枚举。
• 计数数组 ( c )：实时累计 ( F(A) ) 的数量，在计算 ( F(C) ) 后可快速查询满足 ( F(A) \leq F(C) ) 的方案数（复杂度 ( O(26) )，因 ( F(X) \leq 26 )）。

复杂度分析

• 时间复杂度：( O(n \log n) )。枚举 ( p ) 耗时 ( O(n) )，每个 ( p ) 的二分查找耗时 ( O(\log n) )，哈希比较和计数统计均为 ( O(1) ) 或 ( O(26) )，总复杂度为 ( O(n \log n) )，可处理 ( n \leq 2^{20} ) 的数据。
• 空间复杂度：( O(n) )。存储前缀哈希、前缀奇偶状态及计数数组，均为线性空间。

示例说明（样例1）

• 输入字符串 ( S = \text{nnrnnr} )（长度 6）。
• 枚举 ( A ) 的长度 ( p )（1 到 5）：
  • 当 ( p=1 ) 时，( A = \text{n} )，( F(A) = 1 )（仅 'n' 出现 1 次，奇数次）。
  • 二分查找得 ( k=3 )（( A ) 可重复 3 次），计算 ( i=1,2,3 ) 时的 ( F(C) )，累计满足 ( 1 \leq F(C) ) 的方案数。
• 所有 ( p ) 的贡献累加后，总方案数为 8，与样例输出一致。

#include <cstdio>
#include <cstring>
using namespace std;
long long T, I, i, j, len, kk, z[1100000], rr[1100000], ans, s1[100], s2[100], t[100], numh, numa, numq, qa,
     qb;
char s[1100000];
main() {
    //freopen("string.in", "r", stdin);
    //freopen("string.out", "w", stdout);
    scanf("%lld", &T);

    for (I = 1; I <= T; I++) {
        scanf("%s", s + 1);
        len = strlen(s + 1);
        ans = 0;

        for (i = 0; i <= 26; i++) {
            t[i] = 0;
            s1[i] = 0;
            s2[i] = 0;
        }

        kk = 1;

        for (i = 2; i <= len; i++)
            if (kk + z[kk] < i) {
                kk = i;

                for (j = 1; j <= len - i + 1; j++)
                    if (s[j] != s[j + i - 1])
                        break;

                z[i] = j - 1;
            } else {
                z[i] = z[i - kk + 1];

                if (i + z[i] >= kk + z[kk]) {
                    for (j = kk + z[kk] - i + 1; j <= len - i + 1; j++)
                        if (s[j] != s[j + i - 1])
                            break;

                    z[i] = j - 1;
                    kk = i;
                }
            }

        for (i = 2; i < len; i++) {
            rr[i] = z[i + 1] / i + 1;

            if (rr[i]*i == len)
                rr[i]--;
        }

        numa = 0;

        for (i = 1; i <= len; i++) {
            s2[s[i] - 'a' + 1]++;

            if (s2[s[i] - 'a' + 1] % 2 == 1)
                numa++;
            else
                numa--;
        }

        numh = numa;
        qa = 0;
        qb = 0;
        numq = 0;

        for (i = 1; i < len; i++) {
            s2[s[i] - 'a' + 1]--;

            if (s2[s[i] - 'a' + 1] % 2 == 1) {
                numh++;
                qa = qa + t[numh];
            } else {
                qa = qa - t[numh];
                numh--;
            }

            s1[s[i] - 'a' + 1]++;

            if (s1[s[i] - 'a' + 1] % 2 == 1)
                numq++;
            else
                numq--;

            ans = ans + rr[i] / 2 * qb + (rr[i] + 1) / 2 * qa;
            t[numq]++;

            if (numq <= numa)
                qb++;

            if (numq <= numh)
                qa++;
        }

        printf("%lld\n", ans);
    }
}