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
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
            6 #include
          
            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
           
            >1; (j^=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
             
              >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