NOIp2020复赛前日志
组合数和卢卡斯定理
首先写的顺序别搞错了
从\(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} \]Lucas
对于质数\(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)过啦!
接下来要快点打板子了!
- [ ] 线段树
- [ ] 树状数组
- [ ] 树状数组\(O(n)\)预处理
- [ ] ST表
- [ ] LCA
- [ ] \(O(1)\)LCA
- [ ]