某一天发现自己的多项式板子好像全机房最慢唉。
于是找了些博客来学习卡常。
然后喜提目前全机房最快。
如何卡常
取模优化
众所周知 C++ 取模慢得出奇,想优化常数,自然而然想到在取模上下工夫。
曾经为了避免加减取模写了这样的东西:
1 | const int mod = 998244353; |
后来发现加一加减一减比一比也挺慢,于是就有了这样的东西:
1 | const int mod = 998244353; |
大概就是用了下对int
型右移 31 位会使其全部变成符号位的性质。
预处理原根
每次还要根据长度重新处理蝴蝶变换的数组?这里要做大量的乘法和取模,不如直接一次处理出来优化常数。
预处理要 $O(n\log n)$?长度总是 2 的次幂,完全可以只用 $O(n)$。
清空与移动数组
memset
与memcpy
无论是否在-O2
下都有优秀的表现。
DFT时使用64位无符号整数
稍微算算,发现在模数是int
范围内是不会爆unsigned long long
的。
无符号整数在做加减乘的时候会稍微快一些。
模板
1 |
|
即使在你谷巨慢的评测机下都能够跑过机房其他人在你谷评测机还没那么慢的时候跑的 exp 。