LC 3518. 最小回文排列 II

里面计算rank的方法之前没有接触过 https://leetcode.cn/problems/smallest-palindromic-rearrangement-ii/description/

主要是怎么有效求解 $C (n, m)$ . 在这个题目里面这个数值会比较大，所以不能使用类似DP mod的方法来进行求解，只能硬算并且设置cap limit.

在这里说明了应该如何进行计算 https://leetcode.cn/problems/unique-paths/solutions/3062432/liang-chong-fang-fa-dong-tai-gui-hua-zu-o5k32/ $C (n, m) = n / 1 * (n - 2) / 2 * (n - 3) / 3 \dots (n - m + 1) / m$ 这样计算。这样计算可以确保不会出现分数：

也可以这样理解，由于任意连续 i 个数中必然有 i 的倍数，所以上述计算过程均为整除，不会产生小数。

这个方法挺好的，有了这个方法之后就可以计算不同选择对应的rank了。

def comb_count(n: int, m: int):
    m = min(m, n - m)
    res = 1
    for i in range(1, m + 1):
        res = res * (n - i + 1) // i
        if res >= k: break
    return res

def perm_count(sz):
    res = 1
    for i in range(26):
        if cnt[i] == 0: continue
        res *= comb_count(sz, cnt[i])
        if res >= k:
            break
        sz -= cnt[i]
    return res