bzoj 3527 [Zjoi2014] 力 —— FFT

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3527

看了看TJ才推出来式子，还是不够熟练啊；

TJ：https://blog.csdn.net/qq_33929112/article/details/54590319

然后竟然想愚蠢地做 n 遍 FFT 呵呵...其实做一遍就够了，得到的数组的角标就是上限。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

typedef double db;

int const xn=(<<);

db const Pi=acos(-1.0);

int n,lim,rev[xn];

struct com{db x,y;}a[xn],b[xn],q[xn],p[xn],g[xn];

com operator + (com a,com b){return (com){a.x+b.x,a.y+b.y};}

com operator - (com a,com b){return (com){a.x-b.x,a.y-b.y};}

com operator * (com a,com b){return (com){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}

void fft(com *a,int tp)

{

  for(int i=;i<lim;i++)

    if(i<rev[i])swap(a[i],a[rev[i]]);

  for(int mid=;mid<lim;mid<<=)

    {

      com wn=(com){cos(Pi/mid),tp*sin(Pi/mid)};

      for(int j=,len=(mid<<);j<lim;j+=len)

    {

      com w=(com){,};

      for(int k=;k<mid;k++,w=w*wn)

        {

          com x=a[j+k],y=w*a[j+mid+k];

          a[j+k]=x+y; a[j+mid+k]=x-y;

        }

    }

    }

}

int main()

{

  scanf("%d",&n); n--;

  for(int i=;i<=n;i++)

    {

      scanf("%lf",&q[i].x); p[n-i].x=q[i].x;

      if(i)g[i].x=(1.0/i/i);//1.0/i/i

    }

  int l=; lim=;

  while(lim<=n+n)lim<<=,l++;

  for(int i=;i<lim;i++)

    rev[i]=((rev[i>>]>>)|((i&)<<(l-)));

  fft(q,); fft(p,); fft(g,);

  for(int i=;i<lim;i++)a[i]=q[i]*g[i];

  for(int i=;i<lim;i++)b[i]=p[i]*g[i];

  fft(a,-); fft(b,-);

  for(int i=;i<=n;i++)printf("%.3lf\n",a[i].x/lim-b[n-i].x/lim);

  return ;

}