对于多项式取模做法的一点没什么用的卡常小寄巧
查看原帖
对于多项式取模做法的一点没什么用的卡常小寄巧
319995
THUD楼主2024/10/29 20:05

不要再抱着你的多项式模板类不放了!!!

0.记住永远不要试图保持你的类的封装性。
1.由于每次取模的多项式相同,可以先把该多项式反转后的逆求出来,不要每次取模时都求一遍逆。(这是最主要的,亲测速度能快一倍)
2.如果第一点还不行,直接将该多项式先NTT掉,避免每次取模时的一遍重复的NTT。
3.喜欢写类的应注意参数传递时的拷贝常数,多用move和const&。(这点毕竟不在复杂度瓶颈上感觉优化不大)
4.最后注意一下你的复杂度有没有写假,比如可能会有取模后没重新设置多项式长度。

2024/10/29 20:05
加载中...