NTT 的三次变八次优化

就是将 NTT 的域扩到复数。

我不知道高斯整数的其他取模方式，所以巨慢/xk。而且没用。

我们知道高斯整数的神秘取模方式，使得其结果的范数小于除数的一半。然而我们发现这个取模在整数下的结果仍然在整数取模的同余系中！

好很有精神！

我们选取 \(g=3,mod=998244353\)，我们只需要验证 \(\omega_{n}^k=-\omega_{n}^{\frac{n}{2}+k}\)。就大功告成啦！

然后我们写一个这样的程序：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
signed main(){
	ios::sync_with_stdio(0);
	int g=1,p=-1;
	for(int i=1;i<=(mod-1)/2;i++){
		g=g*3;
		int op=round(1.0*g/mod);
		g=g-mod*op;
		p=p*3;
		op=round(1.0*p/mod);
		p=p-mod*op;
		assert(g==-p);
		// assert(g>0);
	}
	cout<<g<<" "<<p;
	return 0;
}

跑出来没有 RE！好！

于是理论上 NTT 可以扩域到高斯整数。然后就可以用类似于 FFT 的三次变两次优化啦！

然后写一发，中间我都不知道我写了什么神秘东西，然后它 TLE 啦！

66pts 记录

说实话，它是正确的我都很惊讶，于是我更有兴趣了。

注意到这里我直接用 __int128 为了在高斯整数运算的时候不会出现溢出。

然后我们直接写一个全部取模的版本：

它居然也是正确的！！！

过于神秘了。

77pts

然后我就不想写了，因为验证这个东西是正确的就已经达到我的目的了，过于神秘了还是。

然后我转念一想，我不是全部取模了吗？那我直接启动原神！把高斯整数的取模直接删掉！

它过了。

？？？？？？？？

AC 记录

然后我把乘法里面的那个取模删掉，它快了 0.4s！！！

2.10s -> 1.64s

这个时候它的效率就和我第一版 NTT 的效率差不多了。

说实话，它能表现成这样，无论是它的正确性或者速度就已经很令我震惊了。

最后那个在 NTT 中只有两层取模的那个优化我就不加了。

现在这个东西就根本不是高斯整数了，就是只是在实部和虚部这两个东西里直接取模，它居然是正确的/xk。

所以虚数神通广大！