题目链接
bzoj3771 Triple
粘一下题面吧还是qwqqqqq，挺好玩的
我们讲一个悲伤的故事。
从前有一个贫穷的樵夫在河边砍柴。
这时候河里出现了一个水神，夺过了他的斧头，说：
“这把斧头，是不是你的？”
樵夫一看：“是啊是啊！”
水神把斧头扔在一边，又拿起一个东西问：
“这把斧头，是不是你的？”
樵夫看不清楚，但又怕真的是自己的斧头，只好又答：“是啊是啊！”
水神又把手上的东西扔在一边，拿起第三个东西问：
“这把斧头，是不是你的？”
樵夫还是看不清楚，但是他觉得再这样下去他就没法砍柴了。
于是他又一次答：“是啊是啊！真的是！”
水神看着他，哈哈大笑道：
“你看看你现在的样子，真是丑陋！”
之后就消失了。
樵夫觉得很坑爹，他今天不仅没有砍到柴，还丢了一把斧头给那个水神。
于是他准备回家换一把斧头。
回家之后他才发现真正坑爹的事情才刚开始。
水神拿着的的确是他的斧头。
但是不一定是他拿出去的那把，还有可能是水神不知道怎么偷偷从他家里拿走的。
换句话说，水神可能拿走了他的一把，两把或者三把斧头。
樵夫觉得今天真是倒霉透了，但不管怎么样日子还得过。
他想统计他的损失。
樵夫的每一把斧头都有一个价值，不同斧头的价值不同。总损失就是丢掉的斧头价值和。
他想对于每个可能的总损失，计算有几种可能的方案。
注意：如果水神拿走了两把斧头a和b，(a,b)和(b,a)视为一种方案。拿走三把斧头时，(a,b,c),(b,c,a),(c,a,b),(c,b,a),(b,a,c),(a,c,b)视为一种方案。
题解
所谓形式幂级数，字面意思理解嘛
构造生成函数A({0,x^{w_1},...x^{w_2},...x^{w_n}}) 幂为价值,洗漱为方案数
那么 , (A^2) 便是两两组合两种的情况,(A^3)便是三三
题目要求无顺序，每一种情况除一个阶乘，然后发现有重复取得情况如({xx}{xxy})
构造一个某把斧头钦定选两次的生成函数B:({0,x^{2w_1},...x^{2w_2},...x^{2w_n}})
三次的C:({0,x^{3w_1},...x^{3w_2},...x^{3w_n}})
对于两斧组合，同一个被选了两次，直接减去B
那么A*B便是包含两个重复斧头的三斧方案，这种组合有3种排列方式({xyx}{xxy}{yxx})所以需要减去(3*A*B)但({xxx})只有一种，多减了两次，便再(+2*C)
fft优化一下
代码
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
inline int read() {
int x = 0;
char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c <= '9' && c >= '0')x = x * 10 + c- '0',c = getchar();
return x ;
}
#define pi acos(-1.0)
struct Complex {
double x,y;
Complex(double a = 0,double b = 0) : x(a),y(b) {};
} ;
Complex operator + (Complex a,Complex b) { return Complex(a.x + b.x,a.y + b.y);}
Complex operator - (Complex a,Complex b) { return Complex(a.x - b.x,a.y - b.y);}
Complex operator * (Complex a,Complex b) { return Complex(a.x * b.x - a.y * b.y,a.x * b.y + a.y * b.x);}
const int maxn = 1000007;
int n;
Complex A[maxn],B[maxn],C[maxn];
void fft(Complex *a,int n,int type) {
for(int i = 0,j = 0;i < n;++ i) {
if(i < j) std::swap(a[i],a[j]);
for(int k = n >> 1;(j ^= k) < k;k >>= 1);
}
for(int m = 2;m <= n;m <<= 1) {
Complex w1 = Complex (cos(2 * pi / m),type * sin(2 * pi / m));
for(int i = 0;i < n;i += m) {
Complex w = Complex(1,0);
for(int k = 0;k < (m >> 1);++ k) {
Complex t = w * a[i + k + (m >> 1)],u = a[i + k];
a[i + k] = u + t;
a[i + k + (m >> 1)] = u - t;
w = w * w1;
}
}
}
}
Complex ans[maxn];
int main() {
n = read(); int lim = 0;
for(int tmp,i = 1;i <= n;++ i) {
tmp = read();
A[tmp] = Complex(1,0);
B[tmp * 2] = Complex(1,0);
C[tmp * 3] = Complex(1,0);
lim = std::max(lim,tmp * 3);
}
for(n = 1;n <= lim;n <<= 1);
fft(A,n,1);
fft(B,n,1);
fft(C,n,1);
for(int i = 0;i < n;++ i)
ans[i] = A[i] + (A[i] * A[i] - B[i]) * Complex(1.0 / 2.0,0) + (A[i] * A[i] * A[i] - A[i] * B[i] * Complex(3.0,0) + Complex(2.0,0) * C[i]) * Complex(1.0 / 6.0,0);
fft(ans,n,-1);
for(int i = 0;i < n;++ i) {
int T = ans[i].x / n + 0.5;
if(T) printf("%d %d
",i,T);
}
return 0;
}