博客

6276. 统计同位异构字符串数目

https://leetcode.cn/problems/count-anagrams/

Solution (组合数学&模逆元)

参考：


含重复字符的全排列个数

模逆元

import java.math.BigInteger;

class Solution {
    public int countAnagrams(String s) {
        final int MOD = 1_000_000_007;
        long[] dp = new long[s.length() + 1];
        long p = 1;
        dp[0] = 1;
        for (int i = 1; i <= s.length(); i++) {
            dp[i] = dp[i - 1] * i % MOD;
        }
        for (String t : s.split(" ")) {
            int[] count = new int[26];
            for (int c : t.toCharArray()) {
                count[c - 'a']++;
            }
            p = p * dp[t.length()] % MOD;
            for (int i : count) {
                p = p * BigInteger.valueOf(dp[i]).modInverse(BigInteger.valueOf(MOD)).intValue() % MOD;
            }
        }
        return (int) p;
    }
}

补充：其实模逆元也可以打个表。