网站公司利润,注册公司名字大全免费,西京一师一优课建设网站,中小企业网站建设如何传送门
解析
算是比较适合的FFT入门题了吧 一个重要的trick#xff1a; 当函数无法表示成卷积时#xff0c;可以把函数翻转过来 然后调一调就又是卷积了 一个重要的注意事项是FFT的lim一定是两多项式相乘结果多项式的项数#xff01; 即使后面的项根本没有用也一样 其他的…传送门
解析
算是比较适合的FFT入门题了吧 一个重要的trick 当函数无法表示成卷积时可以把函数翻转过来 然后调一调就又是卷积了 一个重要的注意事项是FFT的lim一定是两多项式相乘结果多项式的项数 即使后面的项根本没有用也一样 其他的比较简单了 注意下精度即可
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define il inline
const int N1e6100;
const int M150;
const int mod998244353;
const double piacos(-1.0);
inline ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
int n,m,lim,k;
struct node{double x,y;node(double a0,double b0){xa;yb;}
}A[N],B[N],C[N];
il node operator * (node a,node b){return (node){a.x*b.x-a.y*b.y,a.x*b.ya.y*b.x};
}
il node operator (node a,node b){return (node){a.xb.x,a.yb.y};
}
il node operator - (node a,node b){return (node){a.x-b.x,a.y-b.y};
}
int r[N];
il void fft(node *x,int lim,int flag){for(int i0;ilim;i){if(ir[i]) swap(x[i],x[r[i]]);}for(int l1;llim;l1){node o(cos(pi/l),flag*sin(pi/l));for(int st0;stlim;stl1){node t(1,0);for(int j0;jl;j,tt*o){node ux[stj],vt*x[stjl];x[stj]uv;x[stjl]u-v;}}}return;
}
int main(){nread();for(int i1;in;i){scanf(%lf,A[i].x);B[i].x(double)(1.0/i/i);C[n-i].xA[i].x;}int L0,lim1;while(limn1){lim1;L;}for(int i1;ilim;i) r[i](r[i1]1)|((i1)(L-1));fft(A,lim,1);fft(B,lim,1);fft(C,lim,1);for(int i0;ilim;i){A[i]A[i]*B[i];C[i]C[i]*B[i];}fft(A,lim,-1);fft(C,lim,-1);for(int i1;in;i) printf(%lf\n,(A[i].x-C[n-i].x)/lim);return 0;
}
/**/
