Nhận xét #1: Ta định nghĩa frequency của 1 ký tự là số lần xuất hiện của ký tự đó trong xâu, ví dụ như frequency của ký tự "a" trong xâu "abcad" là ~2~. Một xâu là đẹp khi và chỉ khi tồn tại tối đa ~1~ ký tự trong trong xâu có frequency là số lẻ.

Nhận xét #2: Tối đa ~36~ loại ký tự có thể xuất hiện trong xâu ~S~.

Subtask #1 (xâu S chỉ gồm 2 loại ký tự "a" và "b"):

• Dễ thấy một substring là không đẹp nếu như frequency của ~2~ loại ký tự "a" và "b" ở xâu ~S~ trong đoạn ~[l,r]~ đều là số lẻ, nói cách khác một substring là không đẹp nếu nó có độ dài chẵn nhưng số lần xuất hiện của ký tự "a" lại lẻ.

• Ta dễ dàng tính được số substring không đẹp bằng cách xây ~1~ tổng tiền tố trong ~O(n)~ và chia trường hợp để đảm bảo độ dài của substring luôn chẵn, từ đây ta có thể tính loại trừ để ra được số substring đẹp.

Subtask #2 (n ≤ 2000):

• Ta duyệt qua tất cả ~\frac{n \times (n+1)}{2}~ substring của xâu ~S~ và đồng thời duy trì ~1~ mảng để đếm frequency của các loại ký tự, substring ~S[l, r]~ đang xét là đẹp nếu như tồn tại tối đa ~1~ loại ký tự có frequency lẻ trong xâu ~S[l, r]~. Độ phức tạp của cách làm này là ~O(n^2)~.

Subtask #3 :

• Vì có tối đa ~36~ loại ký tự khác nhau và ta chỉ quan tâm đến frequency của chúng là chẵn hay lẻ, ta có thể lưu thông tin vào bitmask với bit thứ ~i~ bằng ~1~ nếu loại ký tự thứ ~i~ có frequency là số lẻ và bằng ~0~ nếu là số chẵn. Gọi ~mask(l, r)~ là hàm trả về bitmask tương ứng của xâu ~S[l, r]~, ta có công thức sau : ~mask(l, r) = mask(1, l-1) \oplus mask(1, r)~ với ~\oplus~ là phép toán XOR .

• Vậy substring ~S[l, r]~ được coi là đẹp nếu như trong biểu diễn nhị nhân của ~mask(l, r)~ có nhiều nhất ~1~ bit bật, nói cách khác với mỗi vị trí ~r~ cố định ta cần đếm xem có bao nhiêu vị trí ~(l-1)~ thỏa mãn : ~mask(1, l-1) \oplus mask(1, r) = 0~ hoặc ~2^k~ (với ~k~ là một số nguyên không âm bất kỳ).

• Vậy ta sẽ duyệt qua từng tiền tố của xâu ~S~, tính bitmask tương ứng của chúng rồi lưu vào cấu trúc dữ liệu std::map, độ phức tạp của cách làm này là ~O(nlogn \times A)~ với ~A~ là số loại ký tự khác nhau (dễ thấy trong bài này ~A = 36~).

Code mẫu

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using ii = pair<ll, ll>;

#define fastIO ios::sync_with_stdio(0); cin.tie(0);
#define fi first
#define se second
#define pb push_back
#define numBit(x) (__builtin_popcountll(1ll * (x)))
#define getBit(x, i) ((x) >> (i) & 1)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define MASK(x) 1ll << (x)

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x > y + eps) {
            x = y;
            return true;
        } else return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x + eps < y) {
            x = y;
            return true;
        } else return false;
    }

const int N = 1e6 + 7, oo = 1e9 + 7;

int n, cnt[40], cnt1[40];
string s;
unordered_map<bitset<36>, int> dp;
map<char, int> idx;

int main() {
    fastIO;
#ifndef ONLINE_JUDGE
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int _cnt = 0; ll ans = 0; bitset<36> init;
    for (char c = 'a'; c <= 'z'; c++) idx[c] = _cnt++;
    for (char c = '0'; c <= '9'; c++) idx[c] = _cnt++;
    cin >> n >> s; s = ' ' + s; dp[init] = 1;
    for (int i = 1, lo = 1; i < sz(s); i++) {
        cnt[idx[s[i]]]++; bitset<36> b; int odd = 0;
        for (int j = 0; j <= 35; j++)
            if ((cnt[j] & 1)) b |= MASK(j), ++odd;
        if (i > 2) {
            cnt1[idx[s[lo]]]++; bitset<36> b1;
            for (int j = 0; j <= 35; j++)
                if ((cnt1[j] & 1)) b1[j] = 1, ++odd;
            dp[b1]++; lo++;
        }
        if (i >= 2) {
            ans += dp[b]; bitset<36> tmp = b;
            for (int j = 0; j <= 35; j++) {
                tmp ^= MASK(j);
                if ((b ^ tmp).count() <= 1 && dp.find(tmp) != dp.end()) ans += dp[tmp];
                tmp ^= MASK(j);
            }
        }
    }
    cout << ans + n;
}