NOIp2020复赛前日志

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写挂了……NOIp2020复赛前日志

upd(19:09)过啦!

记录详情

接下来要快点打板子了!


  • [ ] 线段树
  • [ ] 树状数组
  • [ ] 树状数组\(O(n)\)预处理
  • [ ] ST表
  • [ ] LCA
  • [ ] \(O(1)\)LCA
  • [ ]
上一篇:如何解决MB SD C4无法登录EWA Net的问题?


下一篇:如何解决MB SD C4无法登录EWA Net的问题?