组合数相关

1. 求$A_n^m$的划分数（%MOD）。有递推方程：$dp[i][j]=\sum_{k=0}^{j}dp[i-1][j-k]$，其中$dp[i][j]$为$j$的$i$划分总数。
2. 求$C_n^m$的划分数（%MOD），有递推方程：$dp[i][j]=dp[i][j-1]+dp[i-1][j]$。
   代码如下：
   

    1 int n, m;
    2 int dp[MAX_M + 1][MAX_N + 1];  // DP数组
    3 
    4 int solve() {
    5     dp[0][0] = 1;
    6     for (int i = 1; i <= m; i++) {
    7         for (int j = 0; j <= n; j++) {
    8             if (j - i >= 0) {
    9                 dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % MOD;
   10             } else {
   11                 dp[i][j] = dp[i - 1][j];
   12             }
   13         }
   14     }
   15     return dp[m][n];
   16 }

    

3. 多重集组合数，有 n 种物品，第 i 种有$a_i$个。不同种类的物品可以互相区分但是相同的种类的无法区别。从这些物品中取 m 个有多少种取法。
   递推方程：$dp[i+1][j]=dp[i+1][j-1]+dp[i][j]-dp[i][j-1-a_i]$
   代码如下：
   

    1 int n, m;
    2 int a[MAX_N];
    3 int dp[MAX_N + 1][mAX + M + 1];
    4 
    5 int solve() {
    6     //一个都不取的方法总是只有一种
    7     for (int i = 0; i <= n; i++) {
    8         dp[i][0] = 1;
    9     }
   10     for (int i = 0; i < n; i++) {
   11         for (int j = 1; j <= m; j++) {
   12             if (j - 1 - a[i] >= 0) {
   13                 dp[i + 1][j] =
   14                     (dp[i + 1][j - 1] + dp[i][j] - dp[i][j - 1 - a[i]] + MOD) %
   15                     MOD;
   16             } else {
   17                 dp[i + 1][j] = (dp[i + 1][j - 1] + dp[i][j]) % MOD;
   18             }
   19         }
   20     }
   21     return dp[n][m];
   22 }

    

组合数相关

原文：https://www.cnblogs.com/romaLzhih/p/11415506.html