题目
Description
我们讲一个悲伤的故事。
从前有一个贫穷的樵夫在河边砍柴。
这时候河里出现了一个水神，夺过了他的斧头，说：
“这把斧头，是不是你的？”
樵夫一看：“是啊是啊！”
水神把斧头扔在一边，又拿起一个东西问：
“这把斧头，是不是你的？”
樵夫看不清楚，但又怕真的是自己的斧头，只好又答：“是啊是啊！”
水神又把手上的东西扔在一边，拿起第三个东西问：
“这把斧头，是不是你的？”
樵夫还是看不清楚，但是他觉得再这样下去他就没法砍柴了。
于是他又一次答：“是啊是啊！真的是！”
水神看着他，哈哈大笑道：
“你看看你现在的样子，真是丑陋！”
之后就消失了。
樵夫觉得很坑爹，他今天不仅没有砍到柴，还丢了一把斧头给那个水神。
于是他准备回家换一把斧头。
回家之后他才发现真正坑爹的事情才刚开始。
水神拿着的的确是他的斧头。
但是不一定是他拿出去的那把，还有可能是水神不知道怎么偷偷从他家里拿走的。
换句话说，水神可能拿走了他的一把，两把或者三把斧头。
樵夫觉得今天真是倒霉透了，但不管怎么样日子还得过。
他想统计他的损失。
樵夫的每一把斧头都有一个价值，不同斧头的价值不同。总损失就是丢掉的斧头价值和。
他想对于每个可能的总损失，计算有几种可能的方案。
注意：如果水神拿走了两把斧头a和b，(a,b)和(b,a)视为一种方案。拿走三把斧头时，(a,b,c),(b,c,a),(c,a,b),(c,b,a),(b,a,c),(a,c,b)视为一种方案。
Input
第一行是整数N，表示有N把斧头。
接下来n行升序输入N个数字Ai，表示每把斧头的价值。
Output
若干行，按升序对于所有可能的总损失输出一行x y，x为损失值，y为方案数。
Sample Input
4
4
5
6
7
Sample Output
4 1
5 1
6 1
7 1
9 1
10 1
11 2
12 1
13 1
15 1
16 1
17 1
18 1
HINT
所有数据满足：Ai<=40000
题解
题目就是要求从一堆数中选$1,2,3$个和不同的方案数
卷积几个然后去去重就好了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<algorithm>
using namespace std;
const int MAX=4e5+5;
const double Pi=acos(-1.0);
struct Complex{
double x,y;
Complex(double X=0,double Y=0) {x=X,y=Y;}
}a[MAX],b[MAX],c[MAX];
int n,m,lim=1,L,maxn;
int R[MAX],val[MAX],A[MAX],B[MAX],C[MAX];
Complex operator+ (Complex x,Complex y) {return Complex(x.x+y.x,x.y+y.y);}
Complex operator- (Complex x,Complex y) {return Complex(x.x-y.x,x.y-y.y);}
Complex operator* (Complex x,Complex y) {return Complex(x.x*y.x-x.y*y.y,x.y*y.x+x.x*y.y);}
void FFT(Complex *A,int tt=1)
{
for(int i=0;i<lim;++i)
if(i<R[i]) swap(A[i],A[R[i]]);
for(int i=1;i<lim;i<<=1)
{
Complex w1=Complex(cos(Pi/i),tt*sin(Pi/i));
for(int l=i<<1,j=0;j<lim;j+=l)
{
Complex w=Complex(1,0),x,y;
for(int k=0;k<i;++k,w=w*w1)
x=A[j+k],y=w*A[i+j+k],A[j+k]=x+y,A[i+j+k]=x-y;
}
}
}
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int main()
{
n=read();
for(int i=1;i<=n;++i)
a[A[i]=read()].x=1,maxn=max(maxn,A[i]),++val[A[i]];
while(lim<=maxn*3) lim<<=1,++L;
for(int i=0;i<=lim;++i)
R[i]=(R[i>>1]>>1)|((i&1)<<L-1);
FFT(a);
for(int i=0;i<=lim;++i)
b[i]=a[i]*a[i];
FFT(b,-1);
for(int i=0;i<=2*maxn;++i)
C[i]=int(b[i].x/lim+0.5);
for(int i=1;i<=n;++i)
--C[A[i]<<1];
for(int i=0;i<=lim;++i)
c[i]=a[i]*a[i]*a[i],b[i]=Complex();
FFT(c,-1);
for(int i=0;i<=3*maxn;++i)
B[i]=c[i].x/lim+0.5;
for(int i=1;i<=n;++i)
++b[A[i]<<1].x,B[A[i]*3]+=3;
FFT(b);
for(int i=0;i<=lim;++i)
b[i]=a[i]*b[i];
FFT(b,-1);
for(int i=0;i<=3*maxn;++i)
B[i]-=3*int(b[i].x/lim+0.5);
for(int i=0;i<=3*maxn;++i)
{
val[i]+=B[i]/6+(C[i]>>1);
if(val[i]) printf("%d %d\n",i,val[i]);
}
return 0;
}
