NTT卡常小技巧
查看原帖
NTT卡常小技巧
329682
suibian1234楼主2024/5/4 13:46

设a=n+1,b=n+2,计算a*b时可由

NTT(a),NTT(b),a[i]=a[i]*b[i]

改为

NTT(a),a[i]=a[i]*(a[i]+1)

一次乘法可少一次NTT。仅有b=a+1时正确

2024/5/4 13:46
加载中...