关于组合数

ningago @ 2022-07-03 12:40:23

by liaoyichen @ 2022-07-03 12:41:52

@ningago 预处理阶乘

by Hisaishi_Kanade @ 2022-07-03 12:42:36

@ningago 特殊的好像可以低于线性

by liaoyichen @ 2022-07-03 12:42:36

by m256i @ 2022-07-03 12:45:02

想起来了，模大质数的时候可以分块+平移+任意模数 NTT 在 \Theta(\sqrt{n}\log n) 的时间复杂度内计算阶乘

by liaoyichen @ 2022-07-03 12:46:03

一般不都是 O(n) 预处理阶乘，然后如果模数为质数单次快速幂算逆元 O(\log p)复杂度

by dehsirehC @ 2022-07-03 12:46:31

模数比较小可以 卢卡斯 或者 扩展卢卡斯

by dehsirehC @ 2022-07-03 12:47:42

然后如果 C(n,m) 的 m 比较小可以 O(\min(\sqrt n,m)\log\log m) 大概埃氏筛做

by m256i @ 2022-07-03 12:47:43

by ningago @ 2022-07-03 12:48:47

@liqingyang @该名称已占用 tx orz

by dehsirehC @ 2022-07-03 12:50:09

错了上面的应该是 \max(\sqrt n,m)