高中数学题，排列组合问题，隔板法，把m个1分为n组，相当于用n-1个隔板去分m个1； 注意：20 20这个最大情况先阶乘会爆long long， 因此要边除边乘；

---

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  long long m,n,ans=1,num=1;cin>>m>>n;
  m=m+n-1;n--;
  for(int i=1;i<=n;i++){
    ans*=m;
    m--;
    num*=i;
    if(ans%num==0){
    ans/=num;
    num=1;
    }
  }
  cout<<ans/num;
  return 0;
}

记得开long long。

---

我们直接来证明其一般情形。

证明

对任意不定方程

$$x_1 + x_2 + \cdots + x_n = m$$

且其中

$$\begin{cases} x_1 \geq a_1 \\ x_2 \geq a_2 \\ \quad\ \ \vdots \\ x_n \geq a_n \end{cases} $$

则对不定方程

$$y_1 + y_2 + \cdots + y_n = M$$

其中 $ y_i = x_i - a_i + 1, M = m + n - \displaystyle \sum_{i=1}^n a_i $ 而言，该不定方程的解应该都是正整数，即

$$\begin{cases} y_1 \geq 1 \\ y_2 \geq 1 \\ \quad\ \ \vdots \\ y_n \geq 1 \end{cases} $$

故这相当于在 $M$ 个小球的 $M-1$ 个间隔中插 $n-1$ 个隔板，分出来的 $n$ 个区域中分别有多少小球对应着每个 $y_i$ 的解. 显然 $y_i$ 解的组数和 $x_i$ 解的组数一样多，所以对原不定方程应该有

$$\binom{m + n - \sum_{i=1}^n a_i -1}{n-1}$$

组解。

对于本题，我们要求的 $x_i$ 均为非负整数，也就是所有 $a_i$ 都等于 $0$。因此解的组数为 $\binom{m+n-1}{n-1}$。我们只需要写一个快速计算组合数的程序即可，组合数递推公式都不会的话可以考虑左拐进入南阳理工小学（不是）。

---

#include <cstdio>

long long int com[41][41];

int fillCom(){
    int i,j;
    com[1][0]=1;
    com[1][1]=1;
    for(i = 2; i <= 40; i ++){
        for(j = 1; j < i; j++){
            com[i][j] = com[i-1][j-1] + com[i-1][j];
        }
        com[i][0] = 1;
        com[i][i] = 1;
    }
    return 0;
}

int main(){
    int m,n;
    scanf("%d%d", &m, &n);
    fillCom();
    printf("%lld", com[m+n-1][n-1]);
    return 0;
}