难度: Medium
Submission
运行时间: 77 ms
内存: 17.0 MB
MOD = int(1e9 + 7)
fac = [1]
ifac = [1]
for i in range(1, int(1e4) + 10):
fac.append((fac[-1] * i) % MOD)
ifac.append((ifac[-1] * pow(i, MOD - 2, MOD)) % MOD)
def C(n: int, k: int) -> int:
if n < 0 or k < 0 or n < k:
return 0
return ((fac[n] * ifac[k]) % MOD * ifac[n - k]) % MOD
class Solution:
def countGoodSubsequences(self, s: str) -> int:
ans = 0
book = sorted(Counter(s).values())
for cnt in range(book[-1], 0, -1):
ways = 1
for v in book:
ways *= C(v, cnt) + 1
ways %= MOD
ans += ways - 1
ans %= MOD
return ans
Explain
这个题解通过预计算阶乘和阶乘的逆来计算组合数C(n, k)，用于计算每个字符出现次数的所有可能的组合方式。解法首先统计字符串中每个字符的出现次数，并将这些数值排序存储。对每种可能的出现次数cnt从最大值向1迭代，计算在至少有cnt个字符的情况下，可以形成的所有子序列的方式，并累加到答案中。这种方法通过动态规划的方式，利用组合数学的知识来高效计算结果。
时间复杂度: O(N + M*K)
空间复杂度: O(N)
MOD = int(1e9 + 7)
fac = [1] # 阶乘数组初始化
ifac = [1] # 逆阶乘数组初始化
for i in range(1, int(1e4) + 10):
fac.append((fac[-1] * i) % MOD) # 计算阶乘
ifac.append((ifac[-1] * pow(i, MOD - 2, MOD)) % MOD) # 计算逆阶乘
def C(n: int, k: int) -> int: # 组合数函数
if n < 0 or k < 0 or n < k: # 边界条件检查
return 0
return ((fac[n] * ifac[k]) % MOD * ifac[n - k]) % MOD # 计算C(n, k)
class Solution:
def countGoodSubsequences(self, s: str) -> int: # 主函数
ans = 0 # 答案初始化
book = sorted(Counter(s).values()) # 统计字符频率并排序
for cnt in range(book[-1], 0, -1): # 从最大频率向下遍历
ways = 1 # 初始化组合方式数
for v in book: # 遍历每个字符的频率
ways *= C(v, cnt) + 1 # 计算当前频率下的组合数并累加
ways %= MOD # 取模
ans += ways - 1 # 将计算结果累加到答案中，减1是因为去掉了全空的情况
ans %= MOD # 取模保证不溢出
return ans # 返回结果
Explore
在计算组合数C(n, k)时使用逆阶乘而不是直接使用阶乘相除的主要原因是计算机在处理模运算（特别是大数）时的限制。直接使用阶乘相除可能导致中间结果非常大，从而溢出或失去精度。而模运算的性质要求我们不能直接在模数下进行除法，因此需要使用逆元来代替除法操作。逆元是基于费马小定理的一个概念，当模数为质数时，一个数a的逆元是a^(p-2) mod p，这可以保证在模运算环境下的乘法和除法结果正确。使用逆阶乘数组，我们可以有效地预计算出所有可能需要的逆元，并用它们来计算组合数，确保计算过程在MOD下的正确性和效率。
在解法中对字符频率进行排序是为了优化计算过程，确保在从最大频率cnt开始向下迭代时的计算效率。通过排序，算法可以从最高的频率开始向下计算每个频率层级的可能子序列数，尽可能快地累加较大的组合数，并在计算过程中避免重复的组合数计算。这种方法利用了从高到低的频率分布，使得每次迭代计算的子序列都是基于当前还未计算过的频率，从而提高算法的总体效率和减少不必要的计算。
在组合数学中，C(n, k)定义为从n个不同元素中选择k个元素的方式数。当k > n时，显然无法从n个元素中选出更多的元素，因此C(n, k)为0。同理，n或k为负数在数学上没有实际意义，因此这些情况下组合数也应当为0。这些边界条件的检查是为了确保组合数函数在逻辑上是健全的，并防止程序在运行时产生非法的数学计算或错误的结果。
在主函数中减去1是为了排除所有字符都不被选择的情况，即空子序列的情况。在计算每种字符的频率可能的组合时，包括了每个字符都不被选中的情况（即C(v, 0) = 1），这意味着当所有字符都不被选择时，会有一个额外的情况被计算进去，即空子序列。因此，为了仅统计有效的子序列（至少包含一个字符的子序列），需要在最后的累加结果中减去这个空子序列的情况。