2019西北工业大学程序设计创新实践基地春季选拔赛(重现赛)-D（组合数逆元解法）
题目链接：https://ac.nowcoder.com/acm/contest/553/D
题意：求不定方程的正整数解和非负整数解的个数(mod 1e9+7)。
思路：对于正整数解，利用插板法，即在n个1中间的n-1个空隙中插m-1个板子，得到m个数，即有C(n-1,m-1)个。对于非负整数解，即不定方程x1+x2+...+xm=m+n的正整数解，即有C(m+n-1,m-1)个。然后就需要用逆元解法求组合数了，复杂度为O(n)。
AC代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int Mod=1e9+7; int m,n; LL inv[2000005],f[2000005],finv[2000005]; void init(){ inv[1]=1; for(int i=2;i<=2000000;++i) inv[i]=(Mod-Mod/i)*inv[Mod%i]%Mod; f[0]=finv[0]=1; for(int i=1;i<2000000;++i){ f[i]=f[i-1]*i%Mod; finv[i]=finv[i-1]*inv[i]%Mod; } } LL C(int x,int y){ return f[x]*finv[x-y]%Mod*finv[y]%Mod; //中间一定要取模一次 } int main(){ scanf("%d%d",&m,&n); init(); printf("%lld %lld ",C(n-1,m-1),C(n+m-1,m-1)); return 0; }