3527: [Zjoi2014]力
Time Limit: 30 Sec Memory Limit: 256 MBSec Special Judge
Submit: 2003 Solved: 1196Description
给出n个数qi，给出Fj的定义如下：令Ei=Fi/qi，求Ei.Input
第一行一个整数n。接下来n行每行输入一个数，第i行表示qi。n≤100000，0<qi<1000000000Output
n行，第i行输出Ei。与标准答案误差不超过1e-2即可。
Sample Input
5
4006373.885184
15375036.435759
1717456.469144
8514941.004912
1410681.345880Sample Output
-16838672.693
3439.793
7509018.566
4595686.886
10903040.872HINT
Source
【分析】
这题的卷积没那么好看出来吧？
Ei=Fi/qi
所以$Ej=\sum_{i<j} \dfrac{qi}{(j-i)^2}-\sum_{i>j} \dfrac{qi}{(j-i)^2}+0(i=j)$
容易看出，分子和分母的和是一样的（卷积）
但是当i>j时系数是减，且这个下标是负号，怎么办呢？
弄一个具体例子容易看出来：
说明是负数的时候$F[i]=-\dfrac{1}{i^2}$ 正数的时候$F[i]=\dfrac{1}{i^2}$$F[0]=0$
即$E[n]=\sum A[i]*F[n-i]$,但这里的n-i可以为负，i从1到max，而不是1到n。
所以把下标全部右移n位即可。
即
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define Maxn 100000*8
const double pi=acos(-); struct P
{
double x,y;
P() {x=y=;}
P(double x,double y):x(x),y(y){}
friend P operator + (P x,P y) {return P(x.x+y.x,x.y+y.y);}
friend P operator - (P x,P y) {return P(x.x-y.x,x.y-y.y);}
friend P operator * (P x,P y) {return P(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x);}
}a[Maxn],b[Maxn]; void fft(P *s,int n,int t)
{
if(n==) return;
P a0[n>>],a1[n>>];
for(int i=;i<=n;i+=) a0[i>>]=s[i],a1[i>>]=s[i+];
fft(a0,n>>,t);fft(a1,n>>,t);
P wn(cos(*pi/n),t*sin(*pi/n)),w(,);
for(int i=;i<(n>>);i++,w=w*wn) s[i]=a0[i]+w*a1[i],s[i+(n>>)]=a0[i]-w*a1[i];
} int main()
{
int n,m;
scanf("%d",&n);n--;
m=*n;
for(int i=;i<=n;i++) scanf("%lf",&a[i].x);
for(int j=n;j>=;j--) b[n-j].x=-1.0/j/j;
b[n].x=;
for(int j=;j<=n;j++) b[n+j].x=1.0/j/j;
int nn=;
while(nn<n+m) nn<<=;
fft(a,nn,);fft(b,nn,);
for(int i=;i<=nn;i++) a[i]=a[i]*b[i];
fft(a,nn,-);
for(int i=n;i<=n+n;i++) printf("%.3lf\n",a[i].x/nn);
return ;
}
2017-04-13 14:26:20