BZOJ3771: Triple

3771: Triple

Time Limit: 20 Sec Memory Limit: 64 MB
Submit: 51 Solved: 30
[Submit][Status]

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

题解：

母函数？总之容斥搞一下。

代码：

  1 #include<cstdio>
  2 
  3 #include<cstdlib>
  4 
  5 #include<cmath>
  6 
  7 #include<cstring>
  8 
  9 #include<algorithm>
 10 
 11 #include<iostream>
 12 
 13 #include<vector>
 14 
 15 #include<map>
 16 
 17 #include<set>
 18 
 19 #include<queue>
 20 
 21 #include<string>
 22 
 23 #define inf 1000000000
 24 
 25 #define maxn 200000+5
 26 
 27 #define maxm 200000+5
 28 
 29 #define eps 1e-10
 30 
 31 #define ll long long
 32 
 33 #define pa pair<int,int>
 34 
 35 #define for0(i,n) for(int i=0;i<=(n);i++)
 36 
 37 #define for1(i,n) for(int i=1;i<=(n);i++)
 38 
 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 40 
 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 42 
 43 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)
 44 
 45 #define for5(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
 46 
 47 #define mod 1000000007
 48 
 49 #define lch k<<1,l,mid
 50 
 51 #define rch k<<1|1,mid+1,r
 52 
 53 using namespace std;
 54 
 55 inline int read()
 56 
 57 {
 58 
 59     int x=0,f=1;char ch=getchar();
 60 
 61     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 62 
 63     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
 64 
 65     return x*f;
 66 
 67 }
 68 struct cp
 69 {
 70     double x,y;
 71     cp operator +(cp b){return (cp){x+b.x,y+b.y};}
 72     cp operator -(cp b){return (cp){x-b.x,y-b.y};}
 73     cp operator *(cp b){return (cp){x*b.x-y*b.y,x*b.y+y*b.x};}
 74     cp operator *(double b){return (cp){b*x,b*y};}
 75 };
 76 cp a[maxn],b[maxn],c[maxn],d[maxn];
 77 int n=131072,m,rev[maxn];
 78 const double pi=acos(-1.0);
 79 void  prepare()
 80 {
 81     int len=17;
 82     for0(i,n-1)
 83     {
 84         int j=i,t=0;
 85         for1(k,len)t<<=1,t^=j&1,j>>=1;
 86         rev[i]=t;
 87     }
 88 }
 89 inline void fft(cp x[],int n,int v)
 90 {
 91     for0(i,n-1)if(rev[i]>i)swap(x[i],x[rev[i]]);
 92     for(int i=2;i<=n;i<<=1)
 93     {
 94         cp wn=(cp){cos(2.0*pi/i*v),sin(2.0*pi/i*v)};
 95         for(int j=0;j<n;j+=i)
 96         {
 97            cp w=(cp){1,0};int mid=i>>1;
 98            for0(k,mid-1)
 99              {
100                cp u=x[j+k],v=x[j+k+mid]*w;
101                x[j+k]=u+v;x[j+k+mid]=u-v;
102                w=w*wn;
103              }
104          }
105      }
106      if(v==-1)for0(i,n-1)x[i].x/=n;
107 }
108 
109 int main()
110 
111 {
112 
113     freopen("input.txt","r",stdin);
114 
115     freopen("output.txt","w",stdout);
116 
117     m=read();
118     for1(i,m)
119     {
120         int x=read();
121         a[x].x=b[2*x].x=c[3*x].x=1;
122     }
123     prepare();
124     fft(a,n,1);fft(b,n,1);fft(c,n,1);
125     for0(i,n-1)d[i]=a[i]+(a[i]*a[i]-b[i])*0.5+(a[i]*a[i]*a[i]-a[i]*b[i]*3.0+c[i]*2.0)*(1.0/6.0);
126     fft(d,n,-1);
127     for0(i,n-1)
128     {
129         ll x=d[i].x+0.5;
130         if(x)printf("%d% lld
",i,x);
131     }
132 
133     return 0;
134 
135 }

View Code