abc295D 统计由SS构成的子串个数

给出长为n的数字串，问它存在多少个子串是happy串？happy串指经重排后，可以由两段同样的内容连起来拼成，比如12341234。
数据范围：1<=n<=5E5

哈希判断是否相同，只需要判断各个数字出现的奇偶性即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define per(i,a,b) for(int i=b; i>=a; i--)

struct node {
    int cnt[10];
    node() {
        rep(i,0,9) cnt[i] = 0;
    }
    void add(int x) {
        cnt[x] += 1;
        cnt[x] %= 2;
    }
    int encode() {
        int h = 0;
        rep(i,0,9) {
            h = h * 3 + cnt[i];
        }
        return h;
    }
};
map<int,int> cnt;
string s;
void solve() {
    cin >> s;
    node nd;
    int ans = 0;
    cnt[0] = 1;
    for (auto c : s) {
        nd.add(c-'0');
        int k = nd.encode();
        ans += cnt[k];
        cnt[k] += 1;
    }
    cout << ans << "\n";
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while (t--) solve();
    return 0;
}