传送门

咱用的是拆系数\(FFT\)因为咱真的不会三模数\(NTT\)……

简单来说就是把每一次多项式乘法都改成拆系数\(FFT\)就行了

如果您还不会多项式求逆的左转->这里

顺带一提,因为求逆的时候要乘两次,两次分开乘,否则会像咱一样炸精度

//minamoto
#include<bits/stdc++.h>
#define R register
#define ll long long
#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
R int res,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
char sr[1<<21],z[20];int K=-1,Z=0;
inline void Ot(){fwrite(sr,1,K+1,stdout),K=-1;}
void print(R int x){
if(K>1<<20)Ot();if(x<0)sr[++K]='-',x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++K]=z[Z],--Z);sr[++K]=' ';
}
const int N=5e5+5,P=1e9+7;const double Pi=acos(-1.0);
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
R int res=1;
for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);
return res;
}
struct cp{
double x,y;
cp(double xx=0,double yy=0){x=xx,y=yy;}
inline cp operator +(const cp &b)const{return cp(x+b.x,y+b.y);}
inline cp operator -(const cp &b)const{return cp(x-b.x,y-b.y);}
inline cp operator *(const cp &b)const{return cp(x*b.x-y*b.y,x*b.y+y*b.x);}
inline cp operator *(const double &b)const{return cp(x*b,y*b);}
}A[N],B[N],C[N],D[N],E[N],G[N],F[N],H[N],w[N],a[N],b[N],c[N],d[N];
int r[N];
int n,len;
void FFT(cp *A,int ty,int lim){
fp(i,0,lim-1)if(i<r[i])swap(A[i],A[r[i]]);
for(R int mid=1;mid<lim;mid<<=1)
for(R int j=0;j<lim;j+=(mid<<1))
for(R int k=0;k<mid;++k){
cp x=A[j+k],y=w[mid+k]*A[j+k+mid];
A[j+k]=x+y,A[j+k+mid]=x-y;
}
if(ty==-1){
reverse(A+1,A+lim);
double k=1.0/lim;fp(i,0,lim-1)A[i]=A[i]*k;
}
}
void Mul(cp *a,cp *b,int len,cp *d){
int lim=1,l=0;while(lim<(len<<1))lim<<=1,++l;
fp(i,0,lim-1)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
for(R int i=1;i<lim;i<<=1)fp(k,0,i-1)w[i+k]=cp(cos(Pi*k/i),sin(Pi*k/i));
fp(i,0,len-1){
A[i].x=(ll)(a[i].x+0.5)>>15,B[i].x=(ll)(a[i].x+0.5)&32767;
C[i].x=(ll)(b[i].x+0.5)>>15,D[i].x=(ll)(b[i].x+0.5)&32767;
A[i].y=B[i].y=C[i].y=D[i].y=0;
}fp(i,len,lim-1)A[i]=B[i]=C[i]=D[i]=0;
FFT(A,1,lim),FFT(B,1,lim),FFT(C,1,lim),FFT(D,1,lim);
fp(i,0,lim-1){
F[i]=A[i]*C[i],G[i]=A[i]*D[i]+C[i]*B[i],H[i]=B[i]*D[i];
}
FFT(F,-1,lim),FFT(G,-1,lim),FFT(H,-1,lim);
fp(i,0,lim-1){
d[i].x=(((ll)(F[i].x+0.5)%P<<30)+((ll)(G[i].x+0.5)<<15)+((ll)(H[i].x+0.5)))%P;
d[i].y=0;
}
}
void Inv(cp *a,cp *b,int len){
if(len==1)return b[0].x=ksm(a[0].x,P-2),void();
Inv(a,b,len>>1);
Mul(a,b,len,c);
Mul(c,b,len,d);
fp(i,0,len-1)b[i].x=((ll)(b[i].x+b[i].x-d[i].x)%P+P)%P;
}
int main(){
// freopen("testdata.in","r",stdin);
n=read();fp(i,0,n-1)a[i].x=read();
int len=1;while(len<n)len<<=1;
Inv(a,b,len);
fp(i,0,n-1)print((ll)(b[i].x+0.5)%P);
return Ot(),0;
}

最新文章

  1. [LeetCode] Tenth Line 第十行
  2. 让android项目支持boost 支持c++11
  3. SQL 表 和字符串 互转 (行列互转)
  4. Xen虚拟机克隆实战
  5. [Everyday Mathematics]20150113
  6. CoreAnimation实现一个折线表
  7. FROM CSDN TO CNBLOGS
  8. MVC5 EF6 Bootstrap3 HtmlHelper
  9. iOS HTTP不能正常使用
  10. Nodejs http-proxy代理实战应用
  11. 小程序modal解决
  12. 关于react的分页
  13. 133. leetcode-Clone Graph
  14. SpringJDBC数据库的基本使用
  15. 关于win10下JDK环境变量的配置以及关于JDK的一些说明
  16. CodeM Qualifying Match Q2
  17. [转] Eclipse安装SVN插件
  18. JAVAEE——宜立方商城01:电商行业的背景、商城系统架构、后台工程搭建、SSM框架整合
  19. Hadoop相关笔记
  20. 笔记-django学习链接

热门文章

  1. 特殊例子--JavaScript代码实现图片循环滚动效果
  2. [LeetCode] 698. Partition to K Equal Sum Subsets
  3. Dubbo之生产者
  4. Spring Boot2.0之web开发
  5. 利用javascript动态向网页中添加表格
  6. 夏日户外风景PSD素材
  7. jQuery Validate 插件为表单提供了强大的验证功能
  8. laravel基础课程---14、表单验证(lavarel如何进行表单验证)
  9. Servlet传递数据方式
  10. matplotlib中文显示-微软雅黑