bzoj 3771 Triple —— FFT

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

令多项式的系数是方案数，次数是值；

设 a(x) 为一个物品的多项式，即 a[w[i]].x = 1，b(x) 为两个物品重复的多项式，即 b[w[i]*2].x = 1，c(x) 为三个物品重复的多项式，即 c[w[i]*3].x = 1；

选恰好三个有序物品的答案就是 a(x)^3 - 3*a(x)*b(x)^2 + c(x)，因为要无序，所以再除以 3! = 6；

选恰好两个有序物品的答案就是 a(x)^2 - b(x)，无序再除以 2! = 2；

再加上选一个物品的答案，也就是 c(x)；

多项式也可以算乘方。

代码如下：

#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,rev[xn],lim,l,p[xn],p2[xn];

db ans[xn];

struct com{db x,y;}a[xn],b[xn],c[xn],t[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};}

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return f?ret:-ret;

}

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()

{

  n=rd(); int mx=;

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

    {

      x=rd(); a[x].x=b[x+x].x=c[x+x+x].x=;

      mx=max(mx,x); p[x]=p2[x+x]=;

    }

  lim=;

  while(lim<=*mx)lim<<=,l++;

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

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

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

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

  fft(t,-);

  for(int i=;i<lim;i++)ans[i]=t[i].x/lim;

  for(int i=;i<lim;i++)t[i]=a[i]*b[i];

  fft(t,-);

  for(int i=;i<lim;i++)ans[i]=(ans[i]-*(t[i].x/lim)+c[i].x)/;

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

  fft(t,-);

  for(int i=;i<lim;i++)ans[i]=(ans[i]+(t[i].x/lim-p2[i])/);

  for(int i=;i<lim;i++)ans[i]+=p[i];

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

    {

      if((int)(ans[i]+0.5)==)continue;

      printf("%d %d\n",i,(int)(ans[i]+0.5));

    }

  return ;

}