组合数计算方法(递推公式、乘法逆元)
1.乘法逆元求组合数
组合数的公式定义：C(n,m) = n! / (m!(n-m)!)，从n个里边选m个
//首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
//如果取模的数是质数，可以用费马小定理求逆元
int qmi(int a, int k, int p) // 快速幂模板
{int res = 1;while (k){if (k & 1) res = (LL)res * a % p;a = (LL)a * a % p;k >>= 1;}return res;
}
// 预处理阶乘的余数和阶乘逆元的余数
int main(){fact[0] = infact[0] = 1;for (int i = 1; i < N; i ++ ){fact[i] = (LL)fact[i - 1] * i % mod;infact[i] = qmi(fact[i], mod - 2, mod) % mod;}int t;cin>>t;While(t--){int a,b,;cin>>a>>b;cout<<(ll)fact[a] * infact[b] % mod * infact[a-b]%mod;}
}
2. 递推公式求组合数
C(n,m) = C(n-1,m) + C(n-1,m-1)
// c[a][b] 表示从a个苹果中选b个的方案数
for (int i = 0; i < N; i ++ )for (int j = 0; j <= i; j ++ )if (!j) c[i][j] = 1;else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;