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

· · 题解

似乎大家都是诡异的写法，没有人用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