提醒一个剪枝
查看原帖
提醒一个剪枝
75765
Starlight237楼主2021/9/18 16:12

扩展 lucas 计算组合数的时候,需要先判断 pvp(n)vp(m)vp(nm)p^{v_p(n)-v_p(m)-v_p(n-m)} 是否模 pkp^k 为 0,若为 0 说明整个组合数为 0,则直接返回 0,不需要再计算。

似乎这个剪枝会造成一倍左右的时间差。。。因为没加这个剪枝 TLE 调了一天才发现。。。

(顺便有无老哥解释一下这个为啥影响这么大呀)

2021/9/18 16:12
加载中...