_皎月半洒花 的博客

_皎月半洒花 的博客

反抗命运的镇魂曲停歇之前,你绝对不可以说我懦弱,绝对不可以说我没有殊死一搏。

题解 P5273 【【模板】多项式幂函数 (加强版)】

posted on 2019-08-03 15:19:09 | under 题解 |

似乎大家都是诡异的写法,没有人用 $O(n\log^2 n)$ 去暴力艹这道题。

然而事实上是完全可以卡过去的。我的提交虽然加了-O2#pragma显得十分弟弟,但是其实去掉之后也是很快的。不吹,绝对比大部分的普通 $O(n\log^2n)$ 的NTT跑得快。

那么以下是几个优化的措施:

$\#1$

预处理原根的次幂——卡常利器。

for (i = 0 ; i < 19  ;++ i){
        rr int *rua = gg[i] ; rua[0] = 1 ;
        rr int gi = rua[1] = expow(3, 998244352/(1 << (i + 1))) ;
        for (j = 2 ; j < (1 << i) ; ++ j) rua[j] = 1ll * rua[j - 1] * gi % P ;
    }

然后每次NTT就不需要重新再计算了。

$\#2$

做快速幂的时候注意可以少几次NTT。这点常数优化也是需要的。

while (K){
        NTT(F, M, 1) ;
        if (K & 1){
            NTT(A, M, 1) ;
            for (i = 0 ; i < M ; ++ i) A[i] = 1ll * A[i] * F[i] % P ;
            NTT(A, M, -1) ; for (i = N ; i < M ; ++ i) A[i] = 0 ;
        }
        for (i = 0 ; i < M ; ++ i)
            F[i] = 1ll * F[i] * F[i] % P ; NTT(F, M, -1) ;
        for (i = N ; i < M ; ++ i) F[i] = 0 ; K >>= 1 ;
    }

$\#3$

不用long long.

这其实一个通用的技巧,因为long long一般都比int多好多常数。同时不要强制类型转换而选择1ll*这种形式。实测可以快许多。

祝大家卡常顺利qwq