题解 | #小红的好子序列#

观察数据范围很大只能考虑组合数了

一个合法子序列其实就是分别对于每个字母，都只能出现偶数个的子序列，对应每个字母来说，其出现情况是独立的，我们可以单独计算所有字母子序列的个数，如果一个字母出现了 x 次，其合法子序列的个数就是 C(0,x)+C(2,x)+C(4,x)+C(6,x)…，我们可以直接模拟算出这些组合数，因为计算最多只会有200000次，然后把所有的情况乘起来，记得减一，因为所有字母都不存在的情况不计数

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int __t = 1, n;
string s;
int kp(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
void solve() {
    map<char, int> mp;
    cin >> s;
    for (auto i : s)
        mp[i]++;
    int ans = 1;
    for (auto [k, v] : mp) {
        int sum = 1, cxy = 1;
        for (int i = 1, j = v; i <= v; i++, j--) {
            cxy = cxy * j % mod * kp(i, mod - 2) % mod;
            if (i % 2 == 0)
                sum = (sum + cxy) % mod;
        }
        ans = ans * sum % mod;
    }
    cout << ans - 1 << "\n";
    return;
}
int32_t main() {
#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    // cin >> __t;
    while (__t--)
        solve();
    return 0;
}