点击刷新
3771: Triple
题意
n个斧头，每个斧头的价值都不同(开始时没注意到)，可以取1个，2个，3个斧头组成不同的价值，求每种价值有多少种组成方案（顺序不同算一种）
分析：
生成函数 + 容斥原理 + FFT。
首先对于只取一个的话，那么生成函数就是$A = (x^0 + x^{w_1} + x^{w_2} + x^{w_3}+...+x^{w_n})$（指数为价值，系数为方案数）
那么朴素的求解就是$ans = A+A^2+A^3$
但是顺序不同算一种，所以每一项都除以n!，$ans = \frac{A}{1!}+\frac{A^2}{2!}+\frac{A^3}{3!}$。例如题面中的(a,b)和(b,a)是一样的。
但是这还有一个问题，每把斧头只能拿一次。所以需要减去拿了多次的情况。构造两个分别为一个斧头拿两次，一个斧头拿三次的生成函数，$B = (x^0 + x^{2w_1} + x^{2w_2}+x^{2w_3}+...+x^{2w_n})$ ，$C = (x^0 + x^{3w_1} + x^{3w_2}+x^{3w_3}+...+x^{3w_n})$。
考虑拿两把斧头的方案，减去一把斧头拿了两次的情况，即$\frac{A^2-B}{2}$。
再考虑拿三把斧头的方案，首先减去一个斧头至少拿两次的方案$A∗B$，一个斧头拿两次的方案是会在被统计到三次，形如$(y,x,x),(x,y,x),(x,x,y)$，所以应该减去三次。一个斧头拿了两次的方案 包含了 拿了三次的方案，对于拿三次的方案，只会统计到一次，形如$(x,x,x)$，只减去一次就好了，所以在原式中再加回来两次，即$\frac{A^3-3*A*B+2*C}{3!}$。
所以最后$ans=A+\frac{A^2-B}{2}+\frac{A^3-3*A*B+2*C}{6}$。
参考博客https://www.zgz233.xyz/2017/08/06/bzoj-3771-triple/
代码：
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<iostream> 5 #include<cmath> 6 #include<cctype> 7 8 using namespace std; 9 10 const int N = 150000; 11 const double Pi = acos(-1.0); 12 13 struct Complex { 14 double x, y; 15 Complex() {} 16 Complex(double _x,double _y) {x = _x, y = _y;} 17 }A[N],B[N],C[N],ans[N]; 18 19 Complex operator + (Complex a, Complex b) { 20 return Complex(a.x + b.x, a.y + b.y); 21 } 22 Complex operator - (Complex a, Complex b) { 23 return Complex(a.x - b.x, a.y - b.y); 24 } 25 Complex operator * (Complex a, Complex b) { 26 return Complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); 27 } 28 29 void FFT(Complex *a,int n,int ty) { 30 for (int i=0,j=0; i<n; ++i) { 31 if (i < j) swap(a[i],a[j]); 32 for (int k=n>>1; (j^=k)<k; k>>=1); 33 } 34 for (int m=2; m<=n; m<<=1) { 35 Complex w1 = Complex(cos(2*Pi/m),ty*sin(2*Pi/m)); 36 for (int i=0; i<n; i+=m) { 37 Complex w = Complex(1,0); 38 for (int k=0; k<(m>>1); ++k) { 39 Complex t = w * a[i+k+(m>>1)]; 40 Complex u = a[i+k]; 41 a[i+k] = u + t; 42 a[i+k+(m>>1)] = u - t; 43 w = w * w1; 44 } 45 } 46 } 47 } 48 49 int main() { 50 int m,mx = 0,n = 1; 51 scanf("%d",&m); 52 for (int x,i=1; i<=m; ++i) { 53 scanf("%d",&x); 54 A[x] = Complex(1,0); 55 B[x * 2] = Complex(1,0); 56 C[x * 3] = Complex(1,0); 57 if (x * 3 > mx) mx = x * 3; 58 } 59 while (n < mx) n <<= 1; 60 61 FFT(A,n,1); 62 FFT(B,n,1); 63 FFT(C,n,1); 64 65 Complex c2 = Complex(2,0),c3 = Complex(3,0),c6 = Complex(6,0); 66 Complex t1 = Complex(1.0/2.0,0),t2 = Complex(1.0/6.0,0); 67 68 for (int i=0; i<n; ++i) 69 ans[i] = A[i] + 70 (A[i] * A[i] - B[i]) * t1 + 71 (A[i] * A[i] * A[i] - (A[i] * B[i]) * c3 + C[i] * c2) * t2; 72 73 FFT(ans,n,-1); 74 75 for (int i=0; i<n; ++i) { 76 int Ans = (int)(ans[i].x / n + 0.5); 77 if (Ans) printf("%d %d\n",i,Ans); 78 } 79 80 return 0; 81 }
© 著作权归作者所有
发表评论
