题意

小红定义一个字符串是好串，当且仅当每个字母出现的次数均为偶数。小红拿到了一个字符串，她想知道该字符串有多少子序列是好串？

思路

题目里求的是满足xxx条件的子序列的个数，那每个字母的贡献都可以单独拿出来算了，比如题目样例的ababa 字符串，a出现了3次，b出现了2次，那么对于a来说，从里面选偶数个都可以构成一种答案，对于b来说也同理。

a和b的选择都是独立的，不难想到相乘就是答案。所以先用哈希表统计出每个字母出现的次数。

对于一个字母来说，出现的次数为x，其对答案的贡献是c[x][0] + c[x][2] + c[x][4] + …… ，即组合数里所有的偶数项加起来，根据组合数的性质

C(n,0)+C(n,1)+C(n,2)+...+C(n,r)+....+C(n,n)=2ⁿ

C(n,0)+C(n,2)+C(n,4)+...=C(n,1)+C(n,3)+C(n,5)+...=2^(n-1)

所以直接算2^n-1次方就可以了

注意最后要把所有字母都不选的情况去掉

在算的时候不能去，因为这个字母不选的时候，选别的字母也可以构成合法的答案

代码

package main

import (
    "fmt"
)

func main() {
    const MOD = 1_000_000_007
    var s string 
    fmt.Scan(&s)
    mp := make(map[rune]int)
    for _,ch := range s {
        mp[ch] ++
    }
    ans := 1
    for _,v := range mp {
        tmp := 1
        //一个字母出现了v次 对答案的贡献是多少 
        //可以从其中选任意2的倍数个 C[v][0] + C[v][2] + C[v][4] 
        //2^(n-1)
        for i := 1; i <= v-1 ; i ++ {
            // if i % 2 != 0 {
            //     continue 
            // }
            tmp  = tmp * 2 % MOD
        }
        ans = ans * tmp % MOD
    }
    fmt.Println(ans-1) //减去所有字母都不选
}