P4239 任意模數多項式乘法逆（多項式/ MTT)

P4239 任意模數多項式乘法逆

這個題目簡直就是毒瘤，不過還好我們可以使用vector封裝要不然真的沒法看，現在我們就會用vector封裝MTT了，然後有一個代碼細節就是這裡的求逆還是在模意義下的，是以我們還是需要求逆。

#include<bits/stdc++.h>
#define LL long long
#define FOR(i,a,b) for(register int i=a,end##i=b;i<=end##i;++i)
#define REP(i,a,b) for(register int i=a,end##i=b;i>=end##i;--i)
#define V inline void
#define I inline LL
using namespace std;
I read()
{
	char x='\0';
	LL fh=1,sum=0;
	for(x=getchar();x<'0'||x>'9';x=getchar())if(x=='-')fh=-1;
	for(;x>='0'&&x<='9';x=getchar())sum=sum*10+x-'0';
	return fh*sum;
}
#define plx complex<double>
#define poly vector<plx>
const plx im(0,1);
const int N=4e5+9;
const int mod=1e9+7;
const int M=sqrt(mod);
const double pi=acos(-1);
poly a;
int n,rev[N];
plx wn[N];
V print(poly a)
{
	FOR(i,0,a.size()-1)cout<<a[i]<<' ';
	cout<<endl;//
}
I ksm(int a,int b)
{
	int sum=1;
	while(b)
	{
		if(b&1)sum=1LL*sum*a%mod;
		b>>=1;
		a=1LL*a*a%mod;
	}
	return sum;
}
I inv(int x){return ksm(x,mod-2);}
V polypre(int len)
{
	FOR(i,0,len-1)rev[i]=(rev[i>>1]>>1)|((i&1)*(len>>1));
	FOR(i,0,len-1)wn[i]=plx(cos(pi/len*i),sin(pi/len*i));
}
V NTT(poly &a,int len,int tp)
{
	a.resize(len);
	FOR(i,0,len-1)if(i<rev[i])swap(a[i],a[rev[i]]);
	for(int mid=1;mid<len;mid<<=1)
	{
		for(int i=0;i<len;i+=mid<<1)
		{
			for(int j=0;j<mid;j++)
			{
				plx x=a[i+j],y=a[i+mid+j]*wn[len/mid*j];
				a[i+j]=x+y,a[i+mid+j]=x-y;
			}
		}
	}
	if(tp==-1)
	{
		FOR(i,0,len-1)a[i]/=len;
		reverse(&a[1],&a[len]);
	}
}
V MTT(poly &a,poly &b,int len)
{
	FOR(i,0,len-1)a[i]=a[i]+b[i]*im;
	NTT(a,len,1);
	FOR(i,0,len-1)b[i]=conj(a[i?len-i:0]);
	FOR(i,0,len-1)
	{
		plx x=a[i],y=b[i];
		a[i]=0.5*(x+y);
		b[i]=0.5*(y-x)*im;
	}
}
I num(double x){return (x<0)?(LL)(x-0.5)%mod:(LL)(x+0.5)%mod;}
poly operator*(poly a,poly b)
{
	int n=a.size()+b.size()-1,len=1;
	while(len<n)len<<=1;
	poly a0(len),a1(len),b0(len),b1(len);
	a.resize(len),b.resize(len);
	FOR(i,0,len-1)a0[i]=(LL)a[i].real()/M,a1[i]=(LL)a[i].real()%M;
	FOR(i,0,len-1)b0[i]=(LL)b[i].real()/M,b1[i]=(LL)b[i].real()%M;
	polypre(len);
	
//	print(a0),print(a1),print(b0),print(b1);
	
	MTT(a0,a1,len),MTT(b0,b1,len);
	
//	print(a0),print(a1),print(b0),print(b1);
//	cout<<"polymult"<<endl;//
	FOR(i,0,len-1)
	{
		a[i]=a0[i]*b0[i]+a1[i]*b0[i]*im;
		b[i]=a0[i]*b1[i]+a1[i]*b1[i]*im;
	}
	NTT(a,len,-1),NTT(b,len,-1);
	
//	print(a),print(b);
	
	FOR(i,0,len-1)
	{
//		cout<<M<<endl;//
//		cout<<num(a[i].real())<<' '<<num(a[i].imag())<<' '<<num(b[i].real())<<' '<<num(b[i].imag())<<endl;//
		a[i]=(1LL*M*M*num(a[i].real())%mod+mod
		+1LL*M*(num(a[i].imag())+num(b[i].real()))%mod+mod
		+num(b[i].imag())+mod)%mod;
		assert(a[i].real()>=0);
		assert(a[i].real()<mod);
//		cout<<a[i]<<endl;//
	}
	a.resize(n);
//	print(a);
	return a;
}
poly operator*(int k,poly a)
{
//	cout<<"mult"<<endl;//
	FOR(i,0,a.size()-1)a[i]=k*(LL)a[i].real()%mod;
//	cout<<"mult "<<endl;//
	return a;
}
poly operator+(poly a,poly b)
{
	if(a.size()<b.size())swap(a,b);
	FOR(i,0,b.size()-1)a[i]=(LL)(a[i].real()+b[i].real()+mod)%mod,assert(a[i].real()>=0);
	return a;
}
poly operator-(poly a){FOR(i,0,a.size()-1)a[i]=mod-a[i].real();return a;}
poly operator-(poly a,poly b){return a+(-b);}
poly polyinv(poly a)
{
	int n=a.size(),len=1;
	while(len<n*2)len<<=1;
	poly b={(double)inv((int)a[0].real())},c;
//	print(b);
	a.resize(len);
	for(int i=2;i<len;i<<=1)
	{
		c.resize(i);
		FOR(j,0,i-1)c[j]=a[j];
//		cout<<i<<endl;//
		b=2*b-c*b*b; 
//		print(b);//
		b.resize(i);
	}
	b.resize(n);
	return b;
}
int main()
{
//	freopen("a.out","w",stdout);
	n=read();
	a.resize(n);
	FOR(i,0,n-1)a[i]=read();
//	a=a*a;
//	print(a);
	a=polyinv(a);
	FOR(i,0,n-1)printf("%d%c",(int)a[i].real(),(i==n-1)?'\n':' ');
	return 0;
}
/*
5
1 6 3 4 9

4
1 1 1 1
*/