bzoj3527 [Zjoi2014]力
程序员文章站
2022-05-22 19:23:30
...
Description
给出n个数qi,给出Fj的定义如下:
令Ei=Fi/qi,求Ei.
Input
第一行一个整数n。
接下来n行每行输入一个数,第i行表示qi。
n≤100000,0 < qi < 1000000000
Output
n行,第i行输出Ei。与标准答案误差不超过1e-2即可。
Sample Input
5
4006373.885184
15375036.435759
1717456.469144
8514941.004912
1410681.345880
Sample Output
-16838672.693
3439.793
7509018.566
4595686.886
10903040.872
分析:
因为Ei=Fi/qi
那这道题和qi就没什么关系了
式子就变成了这样:
tip
在进行FFT的时候,注意带入的一定要是fn
在进行完IDFT之后,一定不要忘了/fn
能优化的常数一定要优化了
这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
const double pi=acos(-1.0);
const int N=550001;
struct node{
double x,y;
node (double xx=0,double yy=0)
{
x=xx;y=yy;
}
};
node a[N],b[N],omega[N],a_omega[N];
int n,fn;
double c[N];
node operator +(const node &a,const node &b){return node (a.x+b.x,a.y+b.y);}
node operator -(const node &a,const node &b){return node (a.x-b.x,a.y-b.y);}
node operator *(const node &a,const node &b){return node (a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
void init(int n)
{
for (int i=0;i<n;i++)
{
omega[i]=node(cos(2.0*i*pi/n),sin(2.0*i*pi/n));
a_omega[i]=node(cos(2.0*i*pi/n),-sin(2.0*i*pi/n));
}
}
void FFT(int n,node *a,node *w)
{
int i,j=0,k;
for (i=0;i<n;i++)
{
if (i>j) swap(a[i],a[j]);
for (int l=n>>1;(j^=l)<l;l>>=1);
}
for (i=2;i<=n;i<<=1)
{
int m=i>>1;
for (j=0;j<n;j+=i)
for (k=0;k<m;k++)
{
node z=a[j+k+m]*w[n/i*k];
a[j+k+m]=a[j+k]-z;
a[j+k]=a[j+k]+z;
}
}
}
int main()
{
scanf("%d",&n); n--;
for (int i=0;i<=n;i++) scanf("%lf",&a[i].x); //q
for (int i=0;i<n;i++) b[i].x=(-1.0)/((double)(n-i)*(double)(n-i)); //-h
for (int i=n+1;i<=2*n;i++) b[i].x=-b[2*n-i].x; //b的后半部分是g
fn=1;
int nn=n;
while (fn<=4*n) fn<<=1; //q*g*h*g 长度是4*n
init(fn);
FFT(fn,a,omega); //转成点值表达
FFT(fn,b,omega);
for (int i=0;i<=fn;i++)
a[i]=a[i]*b[i]; //这样只乘一次就完成了q*g-h*g,优化常数
FFT(fn,a,a_omega);
for (int i=0;i<=fn;i++) c[i]=a[i].x/(double)fn; //IDFT
for (int i=nn;i<=2*nn;i++) printf("%lf\n",c[i]);
return 0;
}
上一篇: Linux 及 VIM 常用命令
下一篇: bzoj 4827 礼物(fft)