首页 > 代码库 > 【BZOJ 3771】 3771: Triple (FFT+容斥)

【BZOJ 3771】 3771: Triple (FFT+容斥)

3771: Triple

Time Limit: 20 Sec  Memory Limit: 64 MB
Submit: 547  Solved: 307

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

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.

HINT

所有数据满足:Ai<=40000

 

 

【分析】

  这个小容斥还是挺容易错的哦。。

  仅取一个相同的多项式a

  仅取两个相同的多项式b

  仅取三个相同的多项式c

  则一个:a

  两个:(a*a-b)/2

  三个:(a*a*a-a*b*3+2*c)/6

  用FFT求卷积就好了

 

技术分享
 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<cmath>
 7 using namespace std;
 8 #define Maxn 800010
 9 const double eps=0.000001;
10 const double pi=acos(-1);
11 
12 struct P
13 {
14     double x,y;
15     P() {x=y=0;}
16     P(double x,double y):x(x),y(y){}
17     friend P operator + (P x,P y) {return P(x.x+y.x,x.y+y.y);}
18     friend P operator - (P x,P y) {return P(x.x-y.x,x.y-y.y);}
19     friend P operator * (P x,P y) {return P(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x);}
20     friend P operator * (P x,int y) {return P(x.x*y,x.y*y);}
21     friend P operator / (P x,int y) {return P(x.x/y,x.y/y);}
22 }a[Maxn],b[Maxn],c[Maxn];
23 
24 int R[Maxn],nn;
25 void fft(P *s,int f)
26 {
27     for(int i=0;i<nn;i++) if(i<R[i]) swap(s[i],s[R[i]]);
28     for(int i=1;i<nn;i<<=1)
29     {
30         P wn(cos(pi/i),f*sin(pi/i));
31         for(int j=0;j<nn;j+=i<<1)
32         {
33             P w(1,0);
34             for(int k=0;k<i;k++,w=w*wn)
35             {
36                 P x=s[j+k],y=w*s[j+k+i];
37                 s[j+k]=x+y;s[j+k+i]=x-y;
38             }
39         }
40     }
41     if(f==-1)
42     {
43         for(int i=0;i<=nn;i++)
44         {
45             s[i]=s[i]/nn;
46         }
47     }
48 }
49 
50 int main()
51 {
52     int n,mx=0;
53     scanf("%d",&n);n--;
54     for(int i=0;i<=n;i++)
55     {
56         int x;
57         scanf("%d",&x);
58         a[x].x=1;
59         b[2*x].x=1;
60         c[3*x].x=1;
61         mx=max(mx,x);
62     }
63     nn=1;int ll=0;
64     while(nn<=3*mx) nn<<=1,ll++;
65     for(int i=0;i<=nn;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(ll-1));
66     fft(a,1);
67     fft(b,1);fft(c,1);
68     for(int i=0;i<=nn;i++)
69     {
70         a[i]=a[i]+(a[i]*a[i]-b[i])/2+(a[i]*a[i]*a[i]-a[i]*b[i]*3+c[i])/6;    
71     }
72     fft(a,-1);
73     for(int i=0;i<=nn;i++)
74     {
75         if(int(a[i].x+0.5)){
76             printf("%d %d\n",i,int(a[i].x+0.5));
77         }
78     }
79     return 0;
80 }
View Code

【对拍好垃圾啊。。

 

2017-04-13 20:37:44

  

【BZOJ 3771】 3771: Triple (FFT+容斥)