排列组合数

说明：

> 排列数： > > 从n个物品中不放回地依次选m个物品，考虑顺序，有多少种方案，记作$A^m_n$ > > $A^m_n={{n!}\over{n-m}!}$ > > 组合数: > > 从n个物品中不放回地依次选m个物品，不考虑顺序，有多少种方案，记作$C^m_n$ > > $C^m_n={{n!}\over{m!\times(n-m)!}}$ > > 求组合数常用公式： > > 定义式 > > $C^m_n={{n!}\over{m!\times(n-m)!}}$ > > 当n,m很大时，预处理阶乘和逆元，预处理O(n),求组合数O(1) > > > > 递推式： > > $C^m_n={{n!}\over{m!\times(n-m)!}}={{n!}\over{(m-1)!\times(n-m+1)!}}\times{{n-m+1}\over{m}}=C^{m-1}_n\times{{n-m+1}\over{m}}$ > > > > 杨辉三角： > > $C^m_n={{n!}\over{m!\times(n-m)!}}={{(n-1)!\times(n-m+m)}\over{m!\times(n-m)!}}={{(n-1)!\times(n-m)}\over{m!\times(n-m)!}}+{{(n-1)!\times m}\over{m!\times(n-m)!}}={{(n-1)!}\over{m! \times(n-m-1)!}}+{{(n-1)!}\over{(m-1)!\times(n-m)!}}=C^m_{n-1}+C^{m-1}_{n-1}$ > > 当模数不是质数的时候，预处理$O(n^2)$，求组合数$O(1)$ > > 性质一 > > $C^m_n=C^{n-m}_n$ > > 性质二 > > $C^m_{n+m+1}=\sum^m_{i=0}C^i_{n+i}$ > > > > 用C(n,m)表示。在Java中，可以使用递归或动态规划的方法来计算组合数。

Java代码模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
递归实现版
*/
public static int C(int n, int m) {
    if (n == m || m == 0) {
        return 1;
    } else {
        return C(n-1, m-1) + C(n-1, m);
    }
}

/*
动态规划实现版
*/
public static int C(int n, int m) {
    int[][] dp = new int[n+1][m+1];
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m && j <= i; j++) {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        }
    }
    return dp[n][m];
}