大组合数

组合数

在一定范围内的组合数,可以通过$C^m_n = C^{m-1}_{n-1} + C^{n-1}_m$迭代直接求解

代码:

1
2
3
4
5
6
for (int i = 0; i <= 1000; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
}

大组合数

求 C(n,m) % k ,通常有两种情况

n,m在一定范围内,k上限为长整形

利用公式$C^m_n = \frac{n!}{m!(n-m)!}$来求解,因为有除法的存在,就要用到模逆元的知识。

如果对逆元不了解,我们可以先暂时跨过这一点,假设有inv()这个函数,使得$(a/b)\%k = a*inv(b)\%k$

这样我们使用数组fac[n]预存$n!\%k$,通过一次迭代就可以求出,fac[n] = fac[n-1] * n % k

最终,$C^m_n$=fac[n] * inv( fac[m] * fac[n-m] % k ) % k

除此之外,如果不想频繁的进行逆元运算,可以使用rfac[n]预存$\frac{1}{n!}\%k$,rfac[n] = rfac[n-1] * inv(n) % k

相应结果就变为,$C^m_n$=fac[n] * rfac[m] % k * rfac[n-m] % k

代码(第二种):

n,m上限为长整形,k在一定范围内

用上面的方法,fac[]预存无论时间和空间都无法接受了,这样的情况使用lucas定理来解决问题

lucas定理:$C^m_n = C^{m\%k}_{n\%k}* C^{m/k}_{n/k}\% k$

$C^{m\%k}_{n\%k}$的部分可以通过上面提到的方法来求解,于是就可以递归求解了

代码: