多项式全家桶

\(FFT\)

快速傅里叶变换 卷积 模板

#include<bits/stdc++.h>
#include<complex>
using namespace std;

const int N=1e7+10;
const double Pi=acos(-1);

int read() {

	int x=0,f=1;
	char ch=getchar();
	while(ch<48||ch>57) {
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>=48&&ch<=57) {
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x*f;

}

int n,m,mlog=1,r[N];

void FFT(complex<double> *a,int x) {

	for(int i=0; i<mlog; i++) {
		if(i<r[i]) swap(a[i],a[r[i]]);
	}
	for(int i=1; i<mlog; i<<=1) {

		complex<double> X(cos(Pi/i),sin(Pi/i)*x);
		for(int j=0; j<mlog; j+=(i<<1)) {
			complex<double> Y(1,0);
			for(int k=0; k<i; k++,Y*=X) {
				complex<double> p=a[j+k],q=a[j+k+i]*Y;
				a[j+k]=p+q;
				a[j+k+i]=p-q;
			}
		}

	}

}

complex<double> a[N],b[N];

int main() {

	n=read();
	m=read();
	for(int i=0; i<=n; i++) a[i]=read();
	for(int i=0; i<=m; i++) b[i]=read();

	int t=0;
	for(mlog=1; mlog<=(m+n); mlog<<=1) t++;
	for(int i=0; i<mlog; i++) r[i]=(r[i>>1]>>1)|((i&1)<<(t-1));
	FFT(a,1);
	FFT(b,1);
	for(int i=0; i<=mlog; i++) a[i]*=b[i];
	FFT(a,-1);

	for(int i=0; i<=n+m; i++) printf("%d ",(int)(0.5+a[i].real()/mlog));

	return 0;
}

FFT优化高精度乘法

#include<bits/stdc++.h>
#define int long long
using namespace std;

typedef long long ll;
const int N=1e7+10;
const double Pi=acos(-1);

int read() {

	int x=0,f=1;
	char ch=getchar();
	while(ch<48||ch>57) {
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>=48&&ch<=57) {
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x*f;

}

complex<double> a[N],b[N];
int n,m,mlog=1,r[N],c[N];

void FFT(complex<double> *a,int x) {

	for(int i=0; i<mlog; i++) {
		if(i<r[i]) swap(a[i],a[r[i]]);
	}
	for(int i=1; i<mlog; i<<=1) {

		complex<double> X(cos(Pi/i),sin(Pi/i)*x);
		for(int j=0; j<mlog; j+=(i<<1)) {
			complex<double> Y(1,0);
			for(int k=0; k<i; k++,Y=Y*X) {
				complex<double> p=a[j+k],q=a[j+k+i]*Y;
				a[j+k]=p+q;
				a[j+k+i]=p-q;
			}
		}

	}

}

string s1,s2;

signed main() {

	cin>>s1>>s2;
	int n=s1.length()-1,m=s2.length()-1;
	for(int i=0; i<=n; i++) a[n-i]=s1[i]-48;
	for(int i=0; i<=m; i++) b[m-i]=s2[i]-48;

	int t=0;
	for(mlog=1; mlog<=(m+n); mlog<<=1) t++;
	for(int i=0; i<mlog; i++) r[i]=(r[i>>1]>>1)|((i&1)<<(t-1));
	FFT(a,1);
	FFT(b,1);
	for(int i=0; i<=mlog; i++) a[i]=a[i]*b[i];
	FFT(a,-1);

	for(int i=0; i<=n+m+1; i++) c[i]=(0.5+a[i].real()/mlog);
	for(int i=0; i<=n+m; i++) {
		c[i+1]+=c[i]/10;
		c[i]%=10;
	}
	int k=n+m+1;
	while(c[k]) {
		c[k+1]+=c[k]/10;
		c[k]%=10;
		k++;
	}
	for(int i=k-1; i>=0; i--) printf("%lld",c[i]);

	return 0;
}

\(NTT\)