NTT学习笔记（快速数论变换）

一些概念

欧拉函数$\varphi (n)$

欧拉函数简介

阶

若$g$和$n$互质，则令$g^x\%n=1$的最小正整数$x$称为$g$模$n$的阶。

原根

对于互质的两个正整数$g$和$n$，如果$g$模$n$的阶为$\varphi (n)$，则称$g$为$n$的原根。

求原根

一般的原根都比较小，暴力枚举即可。

NTT

前置知识：快速傅里叶变换（$FFT$）

在$FFT$中，我们选择$n$次单位复根作为$x$的值，因为他们满足消去引理、折半引理、求和引理，所以可以用分治的方法将时间复杂度变为$O(n\log n)$。但因为用了复数，所以在精度上有误差。而在一些题目要求的是带模的多项式乘法，所以$FFT$就用不了了。那么，我们能不能让$x$取整数值，使得这个值也能满足消去引理、折半引理、求和引理呢？

设$\varphi (m)=r\times 2^d$，令$n=2^d$，$x_n^i=x^{\varphi (m)\times i/n}(\mathrm{mod}m)$，其中$i\le n$

则$x_n^i$有以下性质：

1. 消去引理

$$x_{dn}^{dk}=x_n^k(\mathrm{mod}m)$$

证明：$x_{dn}^{dk}=x^{\varphi (m)\times dk/dn}=x^{\varphi (m)\times k/n}=x_n^k(\mathrm{mod}m)$

2. 折半引理

$$(x_n^{k+n/2}{)}^2=x_{n/2}^k(\mathrm{mod}m)$$

证明：$(x_n^{k+n/2}{)}^2=x_n^{2k+n}=x_n^{2k}=x_{n/2}^k(\mathrm{mod}m)$

3. 求和引理

$$\sum _{i=0}^{n-1}(x_n^k{)}^j=0(\mathrm{mod}m)$$

证明：$\sum _{i=0}^{n-1}(x_n^k{)}^j=\frac{1-(x_n^k{)}^n}{1-x_n^k}=\frac{0}{1-x_n^k}=0$

那么，用$x$来代替$FFT$中的$\omega$，其他不变，就可以求带模数的多项式乘法了。

模数的限制

若模数$m=r\times 2^k+1$（其中$r$为奇数，$k$为整数），则多项式乘积的次数不能超过$2^k$。

如果题目没有模数，那也可以取一个较大的模数，保证答案的每一位都小于这个模数，用这个模数来做$NTT$也是可以的。

一些模数的原根

例题

多项式乘法（FFT）

#include<bits/stdc++.h>
using namespace std;
const long long g=3,mod=998244353;
long long w,wn,a1[5000005],a2[5000005];
long long mi(long long t,long long v){
	if(v==0) return 1;
	long long re=mi(t,v/2);
	re=re*re%mod;
	if(v&1) re=re*t%mod;
	return re;
}
void ch(long long *a,int l){
	for(int i=1,j=l/2,k;i<l-1;i++){
		if(i<j) swap(a[i],a[j]);
		k=l/2;
		while(j>=k){
			j-=k;k>>=1;
		}
		j+=k;
	}
}
void ntt(long long *a,int l,int fl){
	for(int i=2;i<=l;i<<=1){
		if(fl==1) wn=mi(g,(mod-1)/i);
		else wn=mi(g,mod-1-(mod-1)/i);
		for(int j=0;j<l;j+=i){
			w=1;
			for(int k=j;k<j+i/2;k++,w=w*wn%mod){
				long long t=a[k],u=w*a[k+i/2]%mod;
				a[k]=(t+u)%mod;
				a[k+i/2]=(t-u+mod)%mod;
			}
		}
	}
	if(fl==-1){
		long long ny=mi(l,mod-2);
		for(int i=0;i<l;i++) a[i]=a[i]*ny%mod;
	}
}
int main()
{
	int n=1,l1,l2;
	scanf("%d%d",&l1,&l2);++l1;++l2;
	while(n<l1+l2) n<<=1;
	for(int i=0;i<l1;i++){
		scanf("%lld",&a1[i]);
	}
	for(int i=0;i<l2;i++){
		scanf("%lld",&a2[i]);
	}
	ch(a1,n);ch(a2,n);
	ntt(a1,n,1);
	ntt(a2,n,1);
	for(int i=0;i<n;i++){
		a1[i]=a1[i]*a2[i]%mod;
	}
	ch(a1,n);
	ntt(a1,n,-1);
	for(int i=0;i<l1+l2-1;i++) printf("%lld ",a1[i]);
	return 0;
}