Leetcode 2842. Count K-Subsequences of a String With Maximum Beauty

[Woodyiiiiiii]

2842. Count K-Subsequences of a String With Maximum Beauty

2842. Count K-Subsequences of a String With Maximum Beauty

组合数学

难点在于：

1. Cnm如何实现？因为涉及到除法，还要取余，这就涉及到逆元了。但这道题数目比较小，所以可以不用考虑逆元。
2. 选完后，如何考虑各种情况的出现？每个数字直接Avalnum，余法考虑用快速幂或者BigInteger的modPow。

逻辑要清晰。

import java.math.BigInteger;

class Solution {
    public int countKSubsequencesWithMaxBeauty(String s, int k) {
        final int MOD = (int) 1e9 + 7;
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }
        TreeMap<Integer, Integer> treeMap = new TreeMap<>(Comparator.reverseOrder());
        int cc = 0;
        for (int i = 0; i < 26; i++) {
            if (cnt[i] > 0) {
                treeMap.merge(cnt[i], 1, Integer::sum);
                cc++;
            }
        }
        if (cc < k) {
            return 0;
        }

        BigInteger ans = BigInteger.ONE;
        for (int key : treeMap.keySet()) {
            int val = treeMap.get(key);
            if (val <= k) {
                BigInteger tmp = BigInteger.valueOf(key);
                tmp = tmp.modPow(BigInteger.valueOf(val), BigInteger.valueOf(MOD));
                ans = ans.multiply(tmp).mod(BigInteger.valueOf(MOD));
            } else {
                ans = ans.multiply(BigInteger.valueOf(combo(val, k)));
                BigInteger tmp = BigInteger.valueOf(key);
                tmp = tmp.modPow(BigInteger.valueOf(k), BigInteger.valueOf(MOD));
                ans = ans.multiply(tmp).mod(BigInteger.valueOf(MOD));
            }
            k -= val;
            if (k <= 0) {
                break;
            }
        }
        return ans.intValue();
    }

    // get m from n randomly
    private int combo(int n, int m) {
        if (m > n) {
            return 0;
        }
        BigInteger res = BigInteger.ONE;
        for (int i = 0; i < m; i++) {
            res = res.multiply(BigInteger.valueOf(n - i));
        }
        for (int i = 1; i <= m; i++) {
            res = res.divide(BigInteger.valueOf(i));
        }
        return res.intValue();
    }
}