rockdu
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
Source
看数据范围，想到构造生成函数。x^i的系数表示损失为i的方案。那么有FFT我们就可以O(n log n)计算了。现在问题是每一次要取不同的斧子，且每种只有一次，考虑容斥。先求出取相同1把、两把、三把斧子的生成函数，分别记为A, B, C。
对于取一把的情况，答案为A
对于取两把的情况，考虑到不能取相同两把，且这里不分先后顺序（为组合意义），容斥一下，去掉顺序。答案为(A* A - B)/2。
对于取三把的情况，考虑到不能取相同的两把，相同两把可以分布在第一把、第二把，第二把、第三把或者第一把、第三把。有三种排列。但是我们会多扣除三把都选的情况，每一种三把都选的情况会被扣除两次。容斥一下，去除排列。答案为(A*A*A - 3*A*B+2*A)/6
#include<cstdio>
#include<cmath>
#include<cstring>
#include<complex>
#include<algorithm>
#define Pi acos(-1)
using namespace std;
const int maxn = 3e5 + 5;
typedef complex<double> E;
E a[maxn], b[maxn], c[maxn];
E n3(3, 0), n2(2, 0), n6(6, 0);
int n, d, m;
namespace Poly {
int R[maxn], N, m2;
E x1[maxn], x2[maxn];
void init(int n) {
for(N = 1; N <= n; N <<= 1) ++m2;
for(register int i = 0; i < N; ++i)
R[i] = (R[i >> 1] >> 1) | ((i & 1) << (m2 - 1));
}
void DFT(E * a, int type) {
for(register int i = 0; i < N; ++i) if(i < R[i]) swap(a[i], a[R[i]]);
for(register int i = 1; i < N; i <<= 1) {
E Wn(cos(Pi / i), sin(Pi * type / i));
for(register int p = i << 1, j = 0; j < N; j += p) {
E w(1, 0);
for(register int k = 0; k < i; ++k, w *= Wn) {
E x = a[j + k], y = a[j + k + i] * w;
a[j + k] = x + y, a[j + k + i] = x - y;
}
}
}
}
}
int main() {
using namespace Poly;
scanf("%d", &n);
for(register int i = 1; i <= n; ++i) {
scanf("%d", &d);
a[d].real() = 1;
b[d << 1].real() = 1;
c[d * 3].real() = 1;
m = max(d * 3, m);
}
init(m);
DFT(a, 1), DFT(b, 1), DFT(c, 1);
for(register int i = 0; i <= N; ++i) {
a[i] = (a[i] * a[i] * a[i] - n3 * a[i] * b[i] + n2 * c[i]) / n6 + (a[i] * a[i] - b[i]) / n2 + a[i];
}
DFT(a, -1);
for(register int i = 0; i <= N; ++i) {
a[i].real() /= N;
if(abs(a[i].real() - 0) > 0.01) printf("%d %d\n", i, (int)(a[i].real() + 0.5));
}
return 0;
}
没有帐号? 立即注册