营销型网站方案ppt,效益型网站,深圳网站建设公司那家好,广东建设信息网站化简之后#xff0c;发现减号左边的式子是一个卷积。右边的式子#xff0c;把一个函数倒序就是卷积#xff0c;分别FFT#xff0c;求解答案。 大佬blog: https://blog.csdn.net/kyleyoung_ymj/article/details/51721495 #include bits/stdc.h
#define pi acos(-1.0… 化简之后发现减号左边的式子是一个卷积。右边的式子把一个函数倒序就是卷积分别FFT求解答案。 大佬blog: https://blog.csdn.net/kyleyoung_ymj/article/details/51721495 #include bits/stdc.h
#define pi acos(-1.0)
const int maxn 3000005;
using namespace std;
struct E{double real,imag;E(double real0,double imag0):real(real),imag(imag){}friend E operator (E A,E B){return E(A.realB.real,A.imagB.imag);}friend E operator -(E A,E B){return E(A.real-B.real,A.imag-B.imag);}friend E operator *(E A,E B){return E(A.real*B.real-A.imag*B.imag,A.imag*B.realA.real*B.imag);}
};
int n,m,L,rev[maxn];
E f[maxn],rf[maxn],g[maxn],e1[maxn],e2[maxn];
void fft(E *a,int ty){for(int i0;in;i)if(irev[i])swap(a[i],a[rev[i]]);for(int i1;in;i1){E wnE(cos(pi/i),ty*sin(pi/i));for(int p(i1),j0;jn;jp){E w(1,0);for(int k0;ki;k,ww*wn){E xa[jk],yw*a[jki];a[jk]xy;a[jki]x-y;}}}if(ty-1)for(int i0;in;i)a[i].real/n;
}
int main(){scanf(%d,n);--n;for(int i0;in;i){double x;scanf(%lf,x);f[i] x;rf[n-i] x;}for(int i1;in;i)g[i]1.0/i/i;//g[0]0mn*2;for(n1;nm;n1)L;for(int i0;in;i)rev[i](rev[i1]1)|((i1)(L-1));fft(f,1);fft(rf,1);fft(g,1);for(int i0;in;i)e1[i]f[i]*g[i];for(int i0;in;i)e2[i]rf[i]*g[i];fft(e1,-1);fft(e2,-1);for(int i0;im/2;i)printf(%.3f\n,e1[i].real-e2[m/2-i].real);
}看起来是个简单题可是第二部分的卷积形式推了半天都不对。。。结果直接。学的网上写法。。。然而这题想到fft就真的简单。 转载于:https://www.cnblogs.com/RRRR-wys/p/8965556.html
