P7114 [NOIP2020] 字符串匹配 解题报告

~~NOIP的蓝题果然还是好难啊啊啊啊~~

前言：

作为一道 NOIP 的真题， 这道题放在 T2 难度并不是特别大，不过考点还是比较偏的，扩展KMP和树状数组的组合，并且还带有一定的思维难度，估计是当年不少人低分的题目，同时也给了一些人翻盘的机会。总而言之， 是道好题。

Description:
将字符串 $s$ 划分成 $(AB)^iC$的形式，并且满足 $A$ 中出现奇数次的字符数小于等于 $C$ 中出现奇数次的字符数。

Solution：
首先发现 $(AB)^i$ 中的 $AB$ 是一个循环节，因此想到枚举循环节的长度。
由于 $A，B，C$ 的长度均大于等于1，所以循环节长度应为 $2 \leq len \leq n-1$。

画个图发现， 对于长度为 $i$ 的前缀， 它最多循环的次数为 $z_{i+1}/i$ 下取整 $+1$。设循环次数为 $k$, $f(i,j)$表示 $s[i:j]$ 中出现奇数次的字符数。 当 $k$ 为奇数时， $F(C) = f(i+1, n)$, 因此只要找到满足 $f(1, j) \leq f(i+1, n)$ 的 $j$ 的个数即可， 然后用乘法原理统计。当 $k$ 为偶数时， $F(A)$ 必然等于 $0$, $F(C) = f(1, n)$。

实现可以采用数据结构维护，本题最好用树状数组。

时间复杂度 $O(n log 27)$。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
    return x * f;
}
const int N = (1 << 20) + 10, C = 26;
int n;
char s[N];
int z[N];
inline void getZ() {
    z[1] = n;
    for (int i = 2, l = 0, r = 0; i <= n; ++ i) {
        if (i <= r) z[i] = min(z[i-l+1], r-i+1);
        while (i + z[i] <= n && s[i+z[i]] == s[z[i] + 1]) ++ z[i];
        if (i + z[i] - 1 > r) r = i + z[i] - 1, l = i; 
    }
}
int tot[C+10], cnt[C+10], c[C+10];
inline int lowbit (int x) {return x & -x;}
inline void add(int x, int v) {for (; x <= C+1; x += lowbit(x)) c[x] += v;}
inline int ask (int x) {int res = 0; for (; x > 0; x -= lowbit(x)) res += c[x]; return res;}
int ans, all, lst, now;
signed main () {
    int T = read(); 
    while (T --) {
        scanf("%s", s + 1); n = strlen(s + 1); 
        for (int i = 1; i <= n; ++ i) z[i] = 0; getZ();
        for (int i = 1; i <= n; ++ i) if (i + z[i] == n + 1) z[i] --;
        for (int i = 1; i <= C+1; ++ i) tot[i] = cnt[i] = c[i] = 0;
        ans = all = lst = now = 0;
        for (int i = 1; i <= n; ++ i) tot[s[i]-'a'+1] ++;
        for (int i = 1; i <= C; ++ i) all += (tot[i] & 1); lst = all;
        for (int i = 1; i <= n; ++ i) {
            if (tot[s[i]-'a'+1] & 1) lst --; else lst ++;
            if (cnt[s[i]-'a'+1] & 1) now --; else now ++;
            tot[s[i]-'a'+1] --; cnt[s[i]-'a'+1] ++;
            if (i > 1 && i < n) {
                int t = z[i+1] / i + 1;
                ans += (t/2) * ask(all+1) + (t - t/2) * ask(lst+1);
            }
            add(now+1, 1);
        }
        printf("%lld\n", ans);
     }
    return 0;
}