似乎大家都是诡异的写法，没有人用$O(n\log^2 n)$去暴力艹这道题。
然而事实上是完全可以卡过去的。我的提交虽然加了`-O2`和`#pragma`~~显得十分弟弟~~，但是其实去掉之后也是很快的。不吹，绝对比大部分的普通$O(n\log^2n)$的NTT跑得快。
那么以下是几个优化的措施：
### $\#1$
预处理原根的次幂——卡常利器。
```cpp
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`。这点常数优化也是需要的。
```cpp
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