题目描述
给出n个数qi,给出Fj的定义如下:
令。试求
。
输入格式
输入文件force.in包含一个整数n,接下来n行每行输入一个数,第i行表示qi。
输出格式
输出文件force.out有n行,第i行输出Ei。与标准答案误差不超过1e-2即可。
题目解析
易得。发现被减数是标准的卷积形式,减数只需要把q数组反向就可变成标准的卷积形式。于是只需正向逆向各作一次卷积,相减即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
/************************************************************** Problem: 3527 User: frank_c1 Language: C++ Result: Accepted Time:3612 ms Memory:20024 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define lowbit(x) (x)&(-x) #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ struct cpx { double x,y; cpx(double a=0,double b=0):x(a),y(b) {} }; cpx operator + (cpx a,cpx b) {return cpx(a.x+b.x,a.y+b.y);} cpx operator - (cpx a,cpx b) {return cpx(a.x-b.x,a.y-b.y);} cpx operator * (cpx a,cpx b) {return cpx(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);} const double pi=acos(-1.0); void DFT(cpx* a,int n,int d=1) { for(int i=(n>>1),j=1;j<n;j++) { if(i<j) swap(a[i],a[j]); int k;for(k=(n>>1);i&k;i^=k,k>>=1); i^=k; } for(int m=2;m<=n;m<<=1) { cpx w=cpx(cos(pi*2/m*d),sin(pi*2/m*d)); for(int i=0;i<n;i+=m) { cpx s=cpx(1,0); for(int j=i;j<(i+(m>>1));j++) { cpx u=a[j],v=s*a[j+(m>>1)]; a[j]=u+v;a[j+(m>>1)]=u-v; s=s*w; } } } if(d==-1) for(int i=0;i<n;i++) a[i].x=a[i].x/n; } const int maxn=(int)(4e5)+5; cpx A[maxn],B[maxn]; double q[maxn],res[maxn]; int main() { int n,len=0; read(n); while((1<<len) < (n<<1)) len++; for(int i=0;i<n;i++) scanf("%lf",&q[i]); for(int i=0;i<n;i++) A[i]=cpx(q[i]); for(int i=1;i<n;i++) B[i]=cpx(1.0/i/i); DFT(A,1<<len);DFT(B,1<<len); for(int i=0;i<(1<<len);i++) A[i]=A[i]*B[i]; DFT(A,1<<len,-1); for(int i=0;i<(1<<len);i++) res[i]=A[i].x; for(int i=0;i<(1<<len);i++) A[i]=cpx(); for(int i=0;i<(1<<len);i++) B[i]=cpx(); for(int i=0;i<n;i++) A[i]=cpx(q[n-i-1]); for(int i=1;i<n;i++) B[i]=cpx(1.0/i/i); DFT(A,1<<len);DFT(B,1<<len); for(int i=0;i<(1<<len);i++) A[i]=A[i]*B[i]; DFT(A,1<<len,-1); for(int i=0;i<n;i++) res[i]-=A[n-i-1].x; for(int i=0;i<n;i++) printf("%.3lf\n",res[i]); return 0; } |