题目描述
我们讲一个悲伤的故事。
从前有一个贫穷的樵夫在河边砍柴。
这时候河里出现了一个水神，夺过了他的斧头，说：
“这把斧头，是不是你的？”
樵夫一看：“是啊是啊！”
水神把斧头扔在一边，又拿起一个东西问：
“这把斧头，是不是你的？”
樵夫看不清楚，但又怕真的是自己的斧头，只好又答：“是啊是啊！”
水神又把手上的东西扔在一边，拿起第三个东西问：
“这把斧头，是不是你的？”
樵夫还是看不清楚，但是他觉得再这样下去他就没法砍柴了。
于是他又一次答：“是啊是啊！真的是！”
水神看着他，哈哈大笑道：
“你看看你现在的样子，真是丑陋！”
之后就消失了。
樵夫觉得很坑爹，他今天不仅没有砍到柴，还丢了一把斧头给那个水神。
于是他准备回家换一把斧头。
回家之后他才发现真正坑爹的事情才刚开始。
水神拿着的的确是他的斧头。
但是不一定是他拿出去的那把，还有可能是水神不知道怎么偷偷从他家里拿走的。
换句话说，水神可能拿走了他的一把，两把或者三把斧头。
樵夫觉得今天真是倒霉透了，但不管怎么样日子还得过。
他想统计他的损失。
樵夫的每一把斧头都有一个价值，不同斧头的价值不同。总损失就是丢掉的斧头价值和。
他想对于每个可能的总损失，计算有几种可能的方案。
注意：如果水神拿走了两把斧头a和b，(a,b)和(b,a)视为一种方案。拿走三把斧头时，(a,b,c),(b,c,a),(c,a,b),(c,b,a),(b,a,c),(a,c,b)视为一种方案。
输入格式
第一行是整数N，表示有N把斧头。
接下来n行升序输入N个数字Ai，表示每把斧头的价值。
输出格式
若干行，按升序对于所有可能的总损失输出一行x y，x为损失值，y为方案数。
样例输入
4
4
5
6
7
样例输出
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.
提示
所有数据满足：Ai<=40000
题意： 从n个物品中选取1个或 2个 或 3个 的价值和是多少 对于一个价值 输出方案数 （方案无顺序要求）
简单讲一下母函数 例如有3个物品 他们的价值是1，2，3
构造一个母函数 f（x） = x^1 + x^2 + x^3 （表示取一件）
下面我来解释一下这个f（x） 指数为物品的价值 每一项前面的系数表示方案数
x^1 表示取一件物品取到价值为 1 的方案数为 1
x^2 表示取一件物品取到价值为 2 的方案数为 1 以此类推
g（x）= x^2 + x^4 + x^6 （表示同一件物品取两次）
z（x）= x^3 + x^6 + x^9 （表示同一件物品取三次）
那么取两次而且方案数不重复的结果是 ( f ( x ) * f ( x ) - g ( x ) ) / 2 （f ( x ) * f ( x ) 会多算了一次取两个相同的方案 所以要减去 ）
取三次的方案就是 （ f ( x ) * f ( x ) * f（x）-3 * f ( x ) * g(x) +2 * z(x) ）/6
(无顺序要求所以要除以一个3的全排列 f (x) * g (x) / 2 多算了的取了两个相同的方案数 因为下面有一个6的分母 所以乘以了一个系数 3
但是这里面还包括了选取了3个都相同的方案 所以要加上 2*z(x))
这里面的多项式的计算就直接通过FFT优化就好了 （FFT板子当作黑盒直接使用就行了）
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#include <set>
#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <vector>
#define pi acos(-1.0)
#define eps 1e-9
#define fi first
#define se second
#define rtl rt<<1
#define rtr rt<<1|1
#define bug printf("******\n")
#define mem(a,b) memset(a,b,sizeof(a))
#define name2str(x) #x
#define fuck(x) cout<<#x" = "<<x<<endl
#define f(a) a*a
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)
#define pf printf
#define FRE(i,a,b) for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b) for(i = a; i < b; i++)+
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define FIN freopen("data.txt","r",stdin)
#define gcd(a,b) __gcd(a,b)
#define lowbit(x) x&-x
#define rep(i,a,b) for(int i=a;i<b;++i)
#define per(i,a,b) for(int i=a-1;i>=b;--i)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 3e5 + ;
const int maxm = maxn * ;
int n, m, a[maxn], b[maxn];
int len, res[maxm], mx; //开大4倍
struct cpx {
double r, i;
cpx ( double r = , double i = ) : r ( r ), i ( i ) {};
cpx operator+ ( const cpx &b ) {
return cpx ( r + b.r, i + b.i );
}
cpx operator- ( const cpx &b ) {
return cpx ( r - b.r, i - b.i );
}
cpx operator* ( const cpx &b ) {
return cpx ( r * b.r - i * b.i, i * b.r + r * b.i );
}
} va[maxm], vb[maxm];
void rader ( cpx F[], int len ) { //len = 2^M,reverse F[i] with F[j] j为i二进制反转
int j = len >> ;
for ( int i = ; i < len - ; ++i ) {
if ( i < j ) swap ( F[i], F[j] ); // reverse
int k = len >> ;
while ( j >= k ) j -= k, k >>= ;
if ( j < k ) j += k;
}
}
void FFT ( cpx F[], int len, int t ) {
rader ( F, len );
for ( int h = ; h <= len; h <<= ) {
cpx wn ( cos ( -t * * pi / h ), sin ( -t * * pi / h ) );
for ( int j = ; j < len; j += h ) {
cpx E ( , ); //旋转因子
for ( int k = j; k < j + h / ; ++k ) {
cpx u = F[k];
cpx v = E * F[k + h / ];
F[k] = u + v;
F[k + h / ] = u - v;
E = E * wn;
}
}
}
if ( t == - ) //IDFT
for ( int i = ; i < len; ++i ) F[i].r /= len;
}
void Conv ( cpx a[], cpx b[], int len ) { //求卷积
FFT ( a, len, );
FFT ( b, len, );
for ( int i = ; i < len; ++i ) a[i] = a[i] * b[i];
FFT ( a, len, - );
}
void gao () {
len = ;
mx = n + m;
while ( len <= mx ) len <<= ; //mx为卷积后最大下标
for ( int i = ; i < len; i++ ) va[i].r = va[i].i = vb[i].r = vb[i].i = ;
for ( int i = ; i < n; i++ ) va[i].r = a[i]; //根据题目要求改写
for ( int i = ; i < m; i++ ) vb[i].r = b[i]; //根据题目要求改写
Conv ( va, vb, len );
for ( int i = ; i < len; ++i ) res[i] += va[i].r + 0.5;
}
int B[maxn], C[maxn], ans[maxm], cnt1[maxm], cnt2[maxm];
int main() {
FIN;
sf ( n );
int maxxA = -;
for ( int i = , x; i < n ; i++ ) {
sf ( x );
a[x]++, b[x]++, ans[x]++;
maxxA = max ( maxxA, x );
B[ * x]++, C[ * x]++;
}
n = m = ++maxxA;
gao();
for ( int i = ; i <= * maxxA ; i++ ) ans[i] += ( res[i] - B[i] ) / , b[i] = res[i], res[i] = ;
m = * maxxA;
gao();
for ( int i = ; i <= * maxxA ; i++ ) cnt1[i] = res[i], res[i] = ;
for ( int i = ; i <= * maxxA ; i++ ) b[i] = B[i];
gao();
for ( int i = ; i <= * maxxA ; i++ ) cnt2[i] = res[i];
for ( int i = ; i <= * maxxA ; i++ ) ans[i] += ( cnt1[i] - * cnt2[i] + * C[i] ) / ;
for ( int i = ; i <= * maxxA ; i++ ) if ( ans[i] ) printf ( "%d %d\n", i, ans[i] );
return ;
}