数论 – 组合数原理及编码运算

组合数计算原理

n个数字中随机选择m个进行全排列，共有 \small A_n^m = C_n^mA_m^m 种排列

或由全排列中选取相同数字时的不同排列 \small A_m^m 次得到下式

组合数计算公式 \small C_n^m = \frac{A_n^m}{A_m^m} = \frac{n!}{m!(n-m)!}

组合数编码

公式模拟阶乘容易超出表示范围，应采用性质避免

乘除交替避免溢出

按以下变形式乘一项除一项，防止乘法溢出

\tiny
\begin{aligned}
C_n^m &= \frac{n!}{m!(n-m)!}\\
&=\frac{(n-m+1)(n-m+2)\cdots n}{m!}\\
&=(\frac{n-m+1}{1}) \cdot (\frac{n-m+2}{2}) \cdots (\frac{n}{m})\\
\end{aligned}

按数字倒序计算时，初始的除数较大，会出现int未整除而导致精度丢失，如 \small C_8^4

// C_8^4 = 60，正确结果为70
public int C(int n, int m) {
    long res = 1;
    for (int i = 0; i < m; i++)
        res = res * (n - i) / (m - i);
    return (int) res;
}

按数字大小升序计算，初始小除数作为被除数因子可以整除

public int C(int n, int m) {
    long res = 1;
    int diff = n - m;
    for (int i = 1; i <= m; i++)
        res = res * (diff + i) / i;
    return (int) res;
}

加法拆分避免溢出

动态规划状态转移方程 \small C_n^m = C_{n-1}^{m-1} + C_{n-1}^{m}

如果选择第n项，则剩余m-1项从n-1项中选出

如果不选择第n项，则m项均从其余n-1项中选出