java 解法, 执行用时: 63 ms, 内存消耗: 40.8 MB, 提交时间: 2023-10-22 09:41:14

class Solution {
    private static long[] factorial; private static int mod = 1_000_000_000 + 7;
    // 实现计算阶乘
    static {
        factorial = new long[10001];
        factorial[0] = 1;
    
        for (int i = 1; i <= 10000; i++) {
            factorial[i] = factorial[i-1] * i;
            factorial[i] %= mod;
        }
    }

    public int countGoodSubsequences(String s) {
        if (s.length() == 0) {
            return 0;
        }
        // 统计26个字符 每个字符穿线的次数 过程中 记录最大出现次数
        int[] count = new int[26];
        int max = 0;
        for (char ch : s.toCharArray()) {
            count[ch - 'a']++;
            max = Math.max(max, count[ch - 'a']);
        }
        // 从 1到 max 出现次数 遍历 每个出现次数，表示每个字母 如果选择的话 要选择的个数
        long totalCount = 0;
        for (int i = 1; i <= max; i++) {
            // 每个字母的个数
            int eachCharCount = i;
            long cur = 1;
            for (int j = 0; j < 26; j++) {
                // 枚举每个字母
                if (count[j] < eachCharCount) {
                    continue;
                }
                // 字母个数足够 从 当前字母个数中选择 eachCharCount 个字母 有多少中组合
                cur += ((cur * combination(count[j], eachCharCount)) % mod);
                cur %= mod;
            }
            totalCount += ((cur-1+mod) % mod);
            totalCount %= mod;
        }
        // 内部 遍历 1-26 每个字母 按照出现个数 算一个组合数字 组合也要加上 不选择的种类数 跟之前的 做乘法
        // 减去所有都不选择的个数
        return (int) totalCount;
    }
    
    
    /**
     * 从 base 获取 target个 组合数量
     * @param base
     * @param target
     * @return
     */
    private long combination(int base, int target) {
        if (target > base) {
            return 0;
        }
        // 小于等于
        long b = multiply(factorial[base - target], factorial[target]);
        return divide(factorial[base], b);
    }
    
    
    /**
     * 带mod的乘法
     * @param a
     * @param b
     * @return
     */
    private long multiply(long a, long b) {
        long res = a * b;
        res %= mod;
        return res;
    }
    
    
    /**
     * 除法带mod
     * @param a
     * @param b
     * @return
     */
    private long divide(long a, long b){
        return multiply(a, inv(b));
    }
    
    /**
     * 求b的倒数的逆元
     * @param target
     * @return
     */
    private long inv(long target) {
        long tmp = target;
        long n = mod - 2;
        // 快速幂方法
        long res = 1;
        while (n > 0) {
            if (n % 2 == 1) {
                res = multiply(res, tmp);
            }
            tmp = multiply(tmp, tmp);
            n /= 2;
        }
        return res;
    }
}

cpp 解法, 执行用时: 32 ms, 内存消耗: 7.6 MB, 提交时间: 2023-10-22 09:38:23

const int MOD = 1e9 + 7;
const int MAXN = 1e4 + 1;

int factorial[MAXN];

int add(int x, int y) {
    x += y;
    while (x >= MOD) x -= MOD;
    while (x < 0) x += MOD;
    return x;
}

int sub(int x, int y) {
    return add(x, -y);
}

int mul(int x, int y) {
    return (x * 1ll * y) % MOD;
}

int binpow(int x, int y) {
    int z = 1;
    while (y) {
        if (y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}

int inv(int x) {
    return binpow(x, MOD - 2);
}

int divide(int x, int y) {
    return mul(x, inv(y));
}

void get_factorial() {
    factorial[0] = 1;
    for (int i = 1; i < MAXN; i++) factorial[i] = mul(i, factorial[i - 1]);
}

int comb(int n, int k) {
    if (k > n) return 0;
    return divide(factorial[n], mul(factorial[n - k], factorial[k]));
}

class Solution {
public:
    Solution() {
        get_factorial();
    }

    int countGoodSubsequences(string s) {
        vector<int> cnt(26, 0);
        for (auto& ch: s) cnt[ch - 'a']++;

        int ans = 0, mx = *max_element(cnt.begin(), cnt.end());
        for (int i = 1; i <= mx; i++) {
            int cur = 1;
            for (auto& c: cnt) {
                if (c < i) continue;
                cur = mul(cur, add(comb(c, i), 1));
            }
            ans = add(ans, cur - 1);
        }
        return ans;
    }
};

python3 解法, 执行用时: 128 ms, 内存消耗: 16.9 MB, 提交时间: 2023-10-22 09:37:34

fact = [1]*20001 #利用python的负数下标，把阶乘本身和逆元放在同一个数组
mod = 10**9+7
for j in range(2,10001):
    fact[j]=fact[j-1]*j%mod
    fact[-j]=pow(fact[j],mod-2,mod) # 理解不了的真心建议死记吧，我也不敢说下次会在啥时候出了

class Solution:
    def countGoodSubsequences(self, s: str) -> int:

        table = defaultdict(int)   #用哈希表计数，这样每种频率就不一定会循环26次了
        for ch in s:
            table[ch]+=1
        
        def cbo(n,m):
            if n<m: return 0 #n<m为非法，这种字母必须放弃
            return fact[n]*fact[-m]*fact[m-n]%mod #分母的部分为逆元，对应fact数组里的负数下标

        vs = list(table.values())
        mx = max(vs) 
        ans = 0

        for p in range(1,mx+1): # 枚举每种频率
            cur = 1
            for v in vs: #枚举每种字母
                cur*= cbo(v,p)+1 
                cur%=mod
            ans+=cur-1 #注意排除空序列
            ans%=mod
        
        return ans