Triple
Time Limit: 20 Sec Memory Limit: 64 MB
Submit: 847 Solved: 482
[Submit][Status][Discuss]
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
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
样例解释
11有两种方案是4+7和5+6，其他损失值都有唯一方案，例如4=4,5=5,10=4+6,18=5+6+7.
5 1
6 1
7 1
9 1
10 1
11 2
12 1
13 1
15 1
16 1
17 1
18 1
样例解释
11有两种方案是4+7和5+6，其他损失值都有唯一方案，例如4=4,5=5,10=4+6,18=5+6+7.
HINT
所有数据满足：Ai<=40000
题解：发现背包用的上？是不可能的，题目中说的是三把斧头，这是FFT优化生成函数的模板题，
然后再去重即可。
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm> #define pi acos(-1)
#define N 40007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,num,L;
int rev[N*];
struct comp
{
double r,v;
comp(){r=v=0.0;}
comp(double x,double y){r=x,v=y;}
friend inline comp operator+(comp x,comp y){return comp(x.r+y.r,x.v+y.v);}
friend inline comp operator-(comp x,comp y){return comp(x.r-y.r,x.v-y.v);}
friend inline comp operator*(comp x,comp y){return comp(x.r*y.r-x.v*y.v,x.r*y.v+x.v*y.r);}
friend inline comp operator/(comp x,int y){return comp(x.r/y,x.v/y);}
}a[N*],b[N*],c[N*]; void FFT(comp *a,int flag)
{
for (int i=;i<num;i++)
if (i<rev[i]) swap(a[i],a[rev[i]]);
for (int i=;i<num;i<<=)
{
comp wn=comp(cos(pi/i),flag*sin(pi/i));
for (int j=;j<num;j+=(i<<))
{
comp w=comp(,);
for (int k=;k<i;k++,w=w*wn)
{
comp x=a[j+k],y=w*a[j+k+i];
a[j+k]=x+y,a[j+k+i]=x-y;
}
}
}
if (flag==-) for (int i=;i<num;i++) a[i].r/=num;
}
int main()
{
n=read();int up=;
for (int i=;i<=n;i++)
{
int x=read();
a[x].r+=1.0;
b[x*].r+=1.0;
c[x*].r+=1.0;
up=max(up,x*);
}
for (num=;num<=up;num<<=,L++);if (L) L--;
for (int i=;i<num;i++) rev[i]=(rev[i>>]>>)|((i&)<<L);
FFT(a,),FFT(b,),FFT(c,);
for (int i=;i<num;i++)
a[i]=a[i]+a[i]*a[i]/-b[i]/+a[i]*a[i]*a[i]/-a[i]*b[i]/+c[i]/;
FFT(a,-); for (int i=;i<num;i++)
{
int x=(int)(a[i].r+0.5);
if (x==) continue;
printf("%d %d\n",i,x);
}
}