FFT | 3 | 数论变换NTT基础

什么是 $NTT$

就是把把 $FFT$ 中所有的单位根换成了整数的单位根，也就是原根的 $n$ 次幂

通常用于求模意义下的多项式卷积

为什么要用 $NTT$

• 保证精度
• 能用来解决模意义下的卷积问题
• 空间更小
• 但速度不一定更优

前置知识

阶

对于满足 $gcd(a,p)=1$ 的正整数对 $a,p$ ，若 $r$ 是使得 $a^r\equiv 1\pmod p$ 成立的最小整数，则称 $r$ 为 $a$ 模 $p$ 的阶

原根

若在正整数对 $a,p$ 中，$a$ 模 $p$ 的阶等于 $\phi§$ ，则称 $a$ 为 $p$ 的原根

原根有一个特殊的性质

若 $a$ 为 $p$ 的原根，则对于任意整数 $k;(1\le k<p)$ ，$\left(a^k\right)\mod p$ 的值两两不相同

$NTT$ 的单位根

现在设我们的原根为 $a$ ，模数为 $p$ ，那么我们现在的单位根就变成了 $\omega_n^k=a^{k(p-1)/n}$

我们来回顾一下 $FFT$ 中要求的单位根的性质

$$
(\omega_n^k)^t=w_n^{tk}\tag{1}
$$

易证

$$
\omega_n^k=\omega_{n/2}^{k/2}\tag{2}
$$

易证

$$
\omega_n^{j+k}=\omega_n^j\cdot\omega_n^k\tag{3}
$$

易证

$$
\omega_n^0=\omega_n^n=1+0i\\
\omega_n^{n/2}=-1+0i\tag{4}
$$

不易证，证不来

$$
w_n^{k+n/2}=-\omega_n^k\tag{5}
$$

证了上面一个就易证了，可惜我证不来

---

实现

貌似没什么好说的，把 $FFT$ 里面的单位根换了，再把除法用乘上逆元代替就好了

代码中用到了一个很常用的大质数和它的逆元：$998244353$ ，原根为 $3$ ，能够在保证很大的范围内不被模掉

#include <cstdio>
#include <cmath>

#define endl '\n'
#define IO(n) freopen(#n".in","r",stdin),freopen(#n".out","w",stdout)
#define USING_R(fn,n) n fn() {static n _R;static char _C;static bool _F;_F=0;_R=0;_C=GG();while((_C<'0'||_C>'9')&&_C!='-'&&_C!='\0')_C=GG();if(_C=='-')_F=1,_C=GG();while(_C>='0'&&_C<='9')_R=(_R<<3)+(_R<<1)+_C-'0',_C=GG();if (_F) _R=-_R;return _R;}
#define USING_F(bufsize) char FGC(){static char Buffer[bufsize],*st=NULL,*en=NULL;if(st==en){en=(st=Buffer)+fread(Buffer,1,bufsize,stdin);if(st==en) return EOF;}return *st++;};
#define USING_T(a) const char* __DATA=a;char TGC(){return *__DATA++;}
#define P(a) cout<<#a"="<<(a)<<endl
#define R Read()
#define GG getchar

#define nmax 10097155
#define MOD 998244353
#define G 3
#define sn(a,b) a^=b^=a^=b
const double PI=acos(-1);

USING_R(Read,int)
int f1[nmax],f2[nmax];
int pos[nmax];
int n,m;
int len;
int rev;
int ksm(long long x, int p) {
	static long long ret;
	ret=1;
	while (p) {
		if (p&1) ret=(ret*x)%MOD;
		x=(x*x)%MOD;
		p>>=1;
	}
	return ret;
}
inline void ntt(int* a, bool inv) {
	register int i,j,k,q;
	static int delta,w,x,y;
	for (i=0;i<len;i++)
		if (i<pos[i])
			a[i]^=a[pos[i]]^=a[i]^=a[pos[i]];
	for (i=1,q=2;i<len;i=q,q<<=1) {
		delta=ksm(G,(MOD-1)/q);
		if (inv) delta=ksm(delta,MOD-2); //delta变为(1/delta)
		for (j=0;j<len;j+=q) {
			w=1;
			for (k=0;k<i;k++,w=(1LL*w*delta)%MOD) {
				x=a[j+k],y=(1LL*a[i+j+k]*w)%MOD;
				a[j+k]=(x+y)%MOD,a[i+j+k]=(x-y+MOD)%MOD;
			}
		}
	}
	if (inv)
		for (i=0;i<len;i++) a[i]=(1LL*a[i]*rev)%MOD;
}
int main() {
	n=R,m=R;
	register int i,j;
	for (i=0;i<=n;i++) f1[i]=R;
	for (i=0;i<=m;i++) f2[i]=R;
	i=j=m+n+1;
	do {
		len=i&(-i);
		i&=~len;
	} while (i);
	if (len^j) len<<=1;
	for (i=1;i<=len;i++) {
		pos[i]=pos[i>>1]>>1;
		if (i&1) pos[i]^=pos[1];
	}
	rev=ksm(len,MOD-2); //预处理len的逆元
	ntt(f1,0),ntt(f2,0);
	for (i=0;i<len;i++) f1[i]=(1LL*f1[i]*f2[i])%MOD;
	ntt(f1,1);
	for (i=0;i<j;i++) printf("%d ",f1[i]);
	return 0;
}

任意模数的 $NTT$

使用多个大质数分别 $NTT$ 最后用 $CRT$ 合并即可，不过常数略大

一般取 $998244353,;1004535809,;469762049$ ，这三个数原根都为 $3$

例题

P4245 【模板】任意模数NTT