NTT

前置知识FFT

原根

这里提一嘴费马小定理：\(a^{p-1}\equiv a^p-1\)

读者自证不难，这里不证

对于\(p,q\in Z\)，如果\(q^i \bmod p(1 \leq i \leq p-1)\)，那么q为p的原根

或者说\(\forall i,j(1 \leq i < j \leq p-1)\)，\(q^i\not\equiv q^j\pmod p\)

原根没什么快速求法，只能暴力枚举判断

通常模数常见的有\(998244353\),\(1004535809\),\(469762049\)

这几个的原根都是\(3\)

就这么点东西？就这么点东西！

NTT

关于NTT，实际上就是利用一些特殊的质数（例如\(998244353\)，这些质数的特征都是可以可以表示 \(q\times 2^k + 1\)的形式）进行模意义下的运算代替浮点复数运算来保证精度，原理是质数原根和复数单位根在DFT运算中具有相同的性质

用这些数去代替FFT中的\(\omega\)，就是NTT

具体操作是，当合并长度\(len=2mid\)时，单位根为\(cos\frac{2\pi}{len}+isin\frac{2\pi}{len}=cos\frac\pi{mid}+isin\frac\pi{mid}\)

而原根即为\(g^\frac{p-1}{len}=g^\frac{p-1}{2mid}\)

大多数\(g=3,p=998244353\)，即可带入计算FFT了

FFT稍稍改一下就行了

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=998244353;
const int g=3;
int power(int x,int k){
	int res=1;
	while(k){
		if(k&1) res=res*x%p;
		x=x*x%p;
		k>>=1;
	}
	return res; 
}
const int N=2097152+114514;
int len1,len2,n=1,k=0;
string a1,b1;
int a[N],b[N]; 
int ans[N],rev[N];
void fft(int *a,int inv){
	for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int mid=1;mid<n;mid<<=1){
		int temp=power(g,(p-1)/(mid*2));
		if(inv==-1) temp=power(temp,p-2);
		for(int i=0;i<n;i+=(mid<<1)){
			int omega=1;
			for(int j=0;j<mid;j++,omega=omega*temp%p){
				int x=a[i+j],y=omega*a[i+j+mid]%p;
				a[i+j]=(x+y)%p,a[i+j+mid]=(x-y+p)%p;
			}
		}
	}
	if(inv==-1){
		int ninv=power(n,p-2);
		for(int i=0;i<n;i++) a[i]=a[i]*ninv%p;
	}
}
main(){
	cin>>a1>>b1;
	len1=a1.length(),len2=b1.length();
	for(int i=0;i<len1;i++) a[i]=a1[len1-i-1]-48;
	for(int i=0;i<len2;i++) b[i]=b1[len2-i-1]-48;
	while(n<len1+len2-1) n<<=1,k++;
	for(int i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
	fft(a,1),fft(b,1);
	for(int i=0;i<n;i++) a[i]*=b[i];
	fft(a,-1);
	for(int i=0;i<n;i++) ans[i]+=(int)(a[i]+0.5),ans[i+1]+=ans[i]/10,ans[i]%=10;
	while(!ans[n]&&n) n--;
	for(int i=n;i>=0;i--) cout<<ans[i];
	return 0;
}