可能不少 FFT 和 NTT 都写得差不多，或许你换个快点的写法就没事了
by hly1204 @ 2020-07-29 19:15:45
@[hly1204](/user/242973) 啊这，我感觉我NTT常数还算正常吧
```cpp
void NTT(ll* a,ll len,ll type)
{
for(ll i=0;i<len;++i)
if(status[i]>i)std::swap(a[status[i]],a[i]);
for(ll cur=1;cur<len;cur<<=1)
{
ll r=Qpow(type==1?3:Inv(3),(mod-1)/(cur<<1));
for(ll j=0;j<len;j+=(cur<<1))
{
ll w=1;
for(ll k=0;k<cur;++k,w=w*r%mod)
{
ll x=a[j+k],y=w*a[j+cur+k];
a[j+k]=(x+y)%mod,a[j+cur+k]=(x-y)%mod;
}
}
}
if(type==-1)
{
ll inv_len=Inv(len);
for(ll i=0;i<len;++i)a[i]=(a[i]*inv_len%mod+mod)%mod;
}
}
```
by 万弘 @ 2020-07-29 19:17:05
NTT 不太好优化吧
by t162 @ 2020-07-29 19:17:31
补：NTT里面都换成int还是被卡常
by 万弘 @ 2020-07-29 19:17:47
@[万弘](/user/73142) 您这每次都求一遍3的逆元...
by t162 @ 2020-07-29 19:18:55
或者预处理单位根的幂？
by t162 @ 2020-07-29 19:19:28
@[Anticyclone](/user/106140) 求$\log_2 3\times 10^5$次逆元，也不在速控步上，没太大影响把？
by 万弘 @ 2020-07-29 19:20:27
emmm
by t162 @ 2020-07-29 19:23:36
拟还可以把那个w预处理了每次可以直接乘减小常数...
by chdy @ 2020-07-29 19:29:01
@[Anticyclone](/user/106140) 现在你说的两个优化都用上了，还有两个点没过
by 万弘 @ 2020-07-29 19:31:20