title
给你一个字符串 s ，它包含一个或者多个单词。单词之间用单个空格 ' ' 隔开。
如果字符串 t 中第 i 个单词是 s 中第 i 个单词的一个 排列 ，那么我们称字符串 t 是字符串 s 的同位异构字符串。
- 比方说，
"acb dfe"是"abc def"的同位异构字符串，但是"def cab"和"adc bef"不是。
请你返回 s 的同位异构字符串的数目，由于答案可能很大，请你将它对 109 + 7 取余 后返回。
示例 1：
输入：s = "too hot"
输出：18
解释：输入字符串的一些同位异构字符串为 "too hot" ，"oot hot" ，"oto toh" ，"too toh" 以及 "too oht" 。
示例 2：
输入：s = "aa"
输出：1
解释：输入字符串只有一个同位异构字符串。
提示：
1 <= s.length <= 105s只包含小写英文字母和空格' '。- 相邻单词之间由单个空格隔开。
solution
方法1： 大数阶乘除法，要用费马小定理。
方法2： 用comb换种思路，原来是阶乘相除，可以通过comb相乘，此时无除法。
MOD = 10 ** 9 + 7
class BigIntDivide:
def mod_inverse(i):
# 调用取模的乘幂运算, pow复杂度是log(exp)即log(MOD)
return pow(i, MOD - 2, MOD)
def divide_mod(a, b):
'''
计算(a/b) % MOD, 除法变乘法，前提是b和MOD互为质数
'''
# 如果有多个b,比如a/b1/b2, 那就可以递归。a*mod_inverse(b1) % mod * mod_inverse(b2) % mod这样
return a * BigIntDivide.mod_inverse(b) % MOD
def divide_mods(a, b=[]):
'''
计算a /(b1*b2*b3) % MOD等形式，前提是b和MOD互为质数
'''
r = a % MOD
for i, v in enumerate(b):
r *= BigIntDivide.mod_inverse(v)
r %= MOD
return r
class Math1:
import functools
@functools.lru_cache(None)
def factorial_mod_cache(n):
if n == 0 or n == 1:
return 1
return Math1.factorial_mod_cache(n - 1) * n % MOD
class Solution:
def countAnagrams(self, s: str) -> int:
d = s.split(' ')
factorial_mod = Math1.factorial_mod_cache
def calcu(x):
import collections
counter = collections.Counter(x)
n = len(x)
return BigIntDivide.divide_mods(factorial_mod(n), [factorial_mod(v) for v in counter.values()])
# print(calcu("too"))
ans = 1
for v in d:
ans *= calcu(v)
ans %= MOD
return ans % MOD
方法2 参考
MOD = 10 ** 9 + 7
class Solution:
def countAnagrams(self, s: str) -> int:
ans = 1
for word in s.split():
n = len(word)
for v in Counter(word).values():
ans *= comb(n, v)
ans %= MOD
n -= v
return ans