给定一个多项式 (F(x)) ，请求出一个多项式 (G(x))， 满足 (F(x) * G(x) equiv 1 ( mathrm{mod:} x^n ))。系数对 (1e9+7) 取模。
这个模数看似平平无奇，实际上鬼畜得很
前置芝士：
由于三模(NTT)慢出天际，我们选择(MTT)
注意预处理单位根和开(long double)之间选一个 这你也全都要？
稍微组合一下就好了，比较难调（?）
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define eps (1e-8)
inline int read()
{
int x=0;char ch,f=1;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=5e5+10,p=1e9+7;
const double pi=acos(-1.0);
int n;
int pos[N];
int f[N],g[N],g2[N];
struct complex
{
double x,y;
complex(double tx=0,double ty=0){x=tx,y=ty;}
inline complex operator + (const complex &t) const { return complex(x+t.x,y+t.y); }
inline complex operator - (const complex &t) const { return complex(x-t.x,y-t.y); }
inline complex operator * (const complex &t) const { return complex(x*t.x-y*t.y,x*t.y+y*t.x); }
inline complex operator * (const double t) const { return complex(x*t,y*t); }
inline complex operator ~ () const { return complex(x,-y); }
}a[N],b[N],c[N],d[N],w[N];
inline int fast(int x,int k)
{
int ret=1;
while(k)
{
if(k&1) ret=ret*x%p;
x=x*x%p;
k>>=1;
}
return ret;
}
inline void fft(int limit,complex *a,int inv)
{
for(int i=0;i<limit;++i)
if(i<pos[i]) swap(a[i],a[pos[i]]);
for(int mid=1;mid<limit;mid<<=1)
{
for(int r=mid<<1,j=0;j<limit;j+=r)
{
for(int k=0;k<mid;++k)
{
complex x=a[j+k],y=w[mid+k]*a[j+k+mid];
a[j+k]=x+y;
a[j+k+mid]=x-y;
}
}
}
}
inline void mtt(int pw,int *f,int *g)
{
int limit=1,len=0;
while(limit<(pw<<1)) limit<<=1,++len;
for(int i=0;i<limit;++i) pos[i]=(pos[i>>1]>>1)|((i&1)<<(len-1));
for(int i=0;i<pw;++i) a[i].x=f[i]>>15,a[i].y=f[i]&32767;
for(int i=pw;i<limit;++i) a[i].x=a[i].y=0;
for(int i=0;i<pw;++i) b[i].x=g[i]>>15,b[i].y=g[i]&32767;
for(int i=pw;i<limit;++i) b[i].x=b[i].y=0;
for(int i=1;i<limit;i<<=1)
{
w[i]=complex(1,0);
for(int j=1;j<i;++j)
w[i+j]=((j&31)==1?(complex){cos(pi*j/i), sin(pi*j/i)}:w[i+j-1]*w[i+1]);
}
fft(limit,a,1);fft(limit,b,1);
for(int i=0;i<limit;++i)
{
static complex q,a0,a1,b0,b1;
q=~a[i?limit-i:0],a0=(a[i]-q)*complex(0,-0.5),a1=(a[i]+q)*0.5;
q=~b[i?limit-i:0],b0=(b[i]-q)*complex(0,-0.5),b1=(b[i]+q)*0.5;
c[i]=a1*b1,d[i]=a1*b0+a0*b1+a0*b0*complex(0,1);
}
reverse(c+1,c+limit);reverse(d+1,d+limit);
fft(limit,c,-1);fft(limit,d,-1);
double k=1.0/limit;
for(int i=0;i<pw;++i) g[i]=(((int)(c[i].x*k+0.5)%p<<30)+((int)(d[i].x*k+0.5)<<15)+(int)(d[i].y*k+0.5))%p;
for(int i=pw;i<limit;++i) g[i]=0;
}
inline void poly_inv(int pw,int *f,int *g)
{
if(pw==1){g[0]=fast(f[0],p-2);return;}
poly_inv((pw+1)>>1,f,g);
for(int i=0;i<pw;++i) g2[i]=g[i];
mtt(pw,f,g2);mtt(pw,g,g2);
for(int i=0;i<pw;++i) g[i]=((2*g[i]-g2[i])%p+p)%p;
}
inline void main()
{
n=read();
for(int i=0;i<n;++i) f[i]=read();
poly_inv(n,f,g);
for(int i=0;i<n;++i) printf("%lld ",(g[i]+p)%p);
}
}
signed main()
{
red::main();
return 0;
}