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

//把出现次数>=2的字符给搞出来，然后对于每个数，只能提取2的倍数或者0个，例如'c'出现8次，那么提取方案就是SUM(C(8,i)) i=0,2,4...8，把所有情况求出来算个乘积，减去所有都是0的情况即可

#include <iostream>
#include <unordered_map>
#include <vector>
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll mod = 1e9+7;
const int maxn = 2e5+5;
ll fact[maxn],inv[maxn];
inline ll Inv(ll n){
    ll p = mod-2;
 	ll res=1LL;
	while(p)
	{
		if(p&1)
			res=res*n%mod;
		n=n*n%mod;
		p>>=1LL;
	}
	return res;   
}
void init()
{
	fact[0]=1LL;
	for(int i=1;i<=200000;i++)
		fact[i]=fact[i-1]*i%mod;
	inv[200000]=Inv(fact[200000]);
	for(int i=199999;i>=0;i--)
		inv[i]=inv[i+1]*(i+1)%mod;
}
int main() {
    init();
    std::string s ;
    std::cin>>s;
    int len = s.size();
    unordered_map<char, int>mp;
    for(int i = 0;i<len;i++){
        mp[s[i]]++;
    }
    vector<ll>vec;
    for(auto it:mp){
        int nums = it.second;
        if(nums<2){
            continue;
        }
        // printf("%d\n",nums);
        ll sum = 0;
        for(int i = 0;i<=nums;i+=2){
            ll tmp = fact[nums]*inv[nums-i]%mod*inv[i]%mod;
            sum  = (sum%mod+tmp%mod)%mod;
            // printf("%lld\n",tmp);
            // tmp%=mod;
        }
        vec.emplace_back(sum);
    }
    ll ans = 1LL;
    for(auto it:vec){
        ans = ans*it%mod;
    }
    ans = (ans+mod-1LL)%mod;
    printf("%lld\n",ans);
    
}
// 64 位输出请用 printf("%lld")