NOIp2020复赛前日志

2024-02-12 08:17:10

组合数和卢卡斯定理

首先写的顺序别搞错了

从\(n\)个不同元素中取出\(m(m≤n)\)个元素的所有组合的个数

\[C_n^m=\binom nm=C(n,m)=\frac{n!}{m!(n-m)!}\\ C_n^0=1\\ C_n^m=C_n^{n-m}=C_{n-1}^{m-1}+C_{n-1}^{m} \]

对于质数\(p\),有

\[\binom{n}{m}\mod p=\binom{n/p}{m/p}\cdot \binom{n\mod p}{m\mod p}\mod p \]

若\(m=0\)返回\(1\)（不然会死循环）

其中的\(\binom{n/p}{m/p}\)不需要再调用卢卡斯函数分解。

需要其他的算法：快速幂求逆元，预处理出阶乘。

注意阶乘预处理时要从\(0\)开始，\(0!=1\).

\[类型空间/8\times 数组大小/1024/1024=空间(MB) \]

例如长度为\(10^6\)的\(int\)数组

\(32\div8\times10^6\div1024\div1024=3.814MB\)

所以如果您有\(512MB\)的话，您可以开\(10^8\)个\(int\)（\(381.4MB\)）也不会\(memory\)爆炸。

而用STL容器的话……最好考虑极限情况并再小二分之一吧。

比如今天我就写The Beautiful Chtholly Tree写挂了……

upd（19：09）过啦！

接下来要快点打板子了！