bzoj3527: [Zjoi2014]力 fft

bzoj3527: [Zjoi2014]力 fft

链接

bzoj

思路

bzoj3527: [Zjoi2014]力 fft

但是我们求得是

\(\sum\limits _{i<j} \frac{q_i}{(i-j)^2}-\sum_{i>j}\frac{q_i}{(i-j)^2}\)

\(\sum\limits _{i<j} \frac{q_i}{(i-j)^2}\)

\(\sum\limits _{i=1}^{j-1} q_i*\frac{1}{(j-i)^2}\)

fft都能算出来

\(\sum\limits _{i=j+1}^{n} q_i*\frac{1}{(i-j)^2}\)

翻转一下fft

具体细节具体看

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4e5+7;
const double Pi=acos(-1.0);
int n,l,limit=1,r[N];
struct Complex {
double x,y;
Complex(double xx=0,double yy=0) {x=xx,y=yy;}
}a[N],b[N],c[N];
Complex operator + (Complex a,Complex b) {return Complex(a.x+b.x,a.y+b.y);}
Complex operator - (Complex a,Complex b) {return Complex(a.x-b.x,a.y-b.y);}
Complex operator * (Complex a,Complex b) {return Complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
void fft(Complex *a,int type) {
for(int i=0;i<limit;++i)
if(i<r[i]) swap(a[i],a[r[i]]);
for(int mid=1;mid<limit;mid<<=1) {
Complex Wn(cos(Pi/mid),type*sin(Pi/mid));
for(int i=0;i<limit;i+=(mid<<1)) {
Complex w(1,0);
for(int j=0;j<mid;++j,w=w*Wn) {
Complex x=a[i+j],y=w*a[i+j+mid];
a[i+j]=x+y;
a[i+j+mid]=x-y;
}
}
}
}
int main() {
scanf("%d",&n);
n--;
for(int i=0;i<=n;++i) scanf("%lf",&a[i].x);
for(int i=1;i<=n;++i) c[n-i].x=b[i].x=1.0/i/i;
while(limit<=n+n) limit<<=1,l++;
for(int i=0;i<=limit;++i)
r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
fft(a,1),fft(b,1),fft(c,1);
for(int i=0;i<=limit;++i) b[i]=a[i]*b[i];
for(int i=0;i<=limit;++i) c[i]=a[i]*c[i];
fft(b,-1),fft(c,-1);
for(int i=0;i<=limit;++i) b[i].x/=limit;
for(int i=0;i<=limit;++i) c[i].x/=limit;
for(int i=0;i<=n;++i) printf("%.3lf\n",b[i].x-c[n+i].x);
return 0;
}
上一篇:jQuery noConflict() 方法----与其他javaScript插件冲突时


下一篇:Spring消息之AMQP.