【Bzoj3771】Triple

来源和评测点

Zjoi2014
Bzoj3771
Caioj1451

题目

【题目大意】
我们讲一个悲伤的故事。
从前有一个贫穷的樵夫在河边砍柴。
这时候河里出现了一个水神,夺过了他的斧头,说:
“这把斧头,是不是你的?”
樵夫一看:“是啊是啊!”
水神把斧头扔在一边,又拿起一个东西问:
“这把斧头,是不是你的?”
樵夫看不清楚,但又怕真的是自己的斧头,只好又答:“是啊是啊!”
水神又把手上的东西扔在一边,拿起第三个东西问:
“这把斧头,是不是你的?”
樵夫还是看不清楚,但是他觉得再这样下去他就没法砍柴了。
于是他又一次答:“是啊是啊!真的是!”
水神看着他,哈哈大笑道:
“你看看你现在的样子,真是丑陋!”
之后就消失了。
樵夫觉得很坑爹,他今天不仅没有砍到柴,还丢了一把斧头给那个水神。
于是他准备回家换一把斧头。
回家之后他才发现真正坑爹的事情才刚开始。
水神拿着的的确是他的斧头。
但是不一定是他拿出去的那把,
还有可能是水神不知道怎么偷偷从他家里拿走的。
换句话说,水神可能拿走了他的一把,两把或者三把斧头。
樵夫觉得今天真是倒霉透了,但不管怎么样日子还得过。
他想统计他的损失。
樵夫的每一把斧头都有一个价值,不同斧头的价值不同。
总损失就是丢掉的斧头价值和。
他想对于每个可能的总损失,计算有几种可能的方案。
注意:如果水神拿走了两把斧头a和b,(a,b)和(b,a)视为一种方案。
拿走三把斧头时,
(a,b,c),(b,c,a),(c,a,b),(c,b,a),(b,a,c),(a,c,b)视为一种方案。
【输入格式】
第一行是整数N,表示有N把斧头。
接下来n行升序输入N个数字Ai,表示每把斧头的价值。
所有数据满足:Ai<=40000
【输出格式】
若干行,按升序对于所有可能的总损失输出一行x y,x为损失值,y为方案数。
【输入样例】
4
4 5 6 7
【输出样例】
4 1
5 1
6 1
8 1
9 1
10 1
11 2
12 1
13 1
14 1
15 1
17 1
18 1
19 1

分析

莫比乌斯反演教程和题目分类参见:
【OI之路】11更高级数论-3快速傅里叶变换
其他快速傅里叶变换题目参见:Tag-快速傅里叶变换

Triple

这道题的精华是容斥
先推荐一下同学的博客,相当严谨科学
他和我的思路不同,属于两种不同的角度
我的思路可能有些乱啊,因为其实是在别人不停点醒才想到的,并不断完善

题意:给出价格各不相同(这很重要)的一些斧头,每次选一、二、三个,将所有方案统计起来,按价格输出,注意选的是组合不是排列。
考虑分解成子问题。

选一个

先解决选一个的情况。
设$q_i$表示第i个斧头的价格。
再设$A(q_i)=1$
则$Ans[i]+=A(q_i)$
原因就是每个斧头选自己,很好理解的

选两个

答案是$A^2(q_i)$吗?
先想想这个式子怎么来的:
将A想成多项式的系数
系数(原本1)相乘就是方案数相乘
指数(价格)相加就是花费相加

然而,仔细考虑,发现不完整,因为会有违法情况
违法1:第i项和第i项相乘,应该被忽略的
违法2:第i、j项乘积和第j、i项乘积重复
对于违法1,设$B(2q_i)=1$,$A^2(q_i)-B(q_i)$
对于违法2,解决违法一后除以2即可
综上所述,$Ans[i]+=\frac { A^2(q_i)-B(q_i) }{2}$

选三个

依照选两个的思路,先计算出$A^3(q_i)$
违法1:aab aba baa
违法2:abc acb bac bca cab cba
对于违法1,
设$AB()=A() \times B(),C(q_i \times 3)=1$,
答案就是$A^3(q_i)-3AB(q_i)+2C(i)$
(因为B是相当于选了两个相同的,所有三个中两个相同情况都应去除)
但假如b=a,也就是aaa,那就不能减3个而是一个,用C补回差值
对于违法2,解决违法一后除以6即可
综上所述,$Ans[i]+=\frac { A^3(q_i)-3AB(q_i)+2C(i) }{6}$

总结与提醒

0次项系数是0,所以$A^3(q_i)$必定是选了三个
$Ans[i]=A(q_i)+\frac{A^2(q_i)-B(q_i)}{2}+\frac { A^3(q_i)-3AB(q_i)+2C(i) }{6}$

对于多项式乘积,使用FFT计算,综合复杂度$\Theta(nlogn)$

嗯我知道我的非常不严谨啦~总而言之就是这样

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
//Zory-2017
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
//*******************全局常量*******************
const double PI=acos(-1.0);
const int MAXN=300000;
//*******************全局定义*******************
struct complex
{
double r,i;//real,imag
complex() {r=i=0;}
complex(double rr,double ii) {r=rr;i=ii;}
complex operator + (complex b) {return complex(r+b.r,i+b.i);}
complex operator - (complex b) {return complex(r-b.r,i-b.i);}
complex operator * (complex b) {return complex(r*b.r-i*b.i,r*b.i+i*b.r);}
//(a+bi)(c+di)=ac+adi+bci+bdi^2=(ac-bd)+(ad+bc)i
//baike.baidu.com/item/复数运算法则
};
//*******************实现*******************
complex omega[MAXN+10];
void CalcOmega(int n,int op)
{
double t=2*PI*op/n;
omega[0]=complex(1,0);
omega[1]=complex(cos(t),sin(t));
for(int k=2;k<=n/2-1;k++) omega[k]=omega[k-1]*omega[1];
}
int R[MAXN+10];
void fft(complex *a,int n,int op)
{
for(int i=0;i<=n-1;i++) if(i<R[i]) swap(a[i],a[R[i]]);
//注意判断大小不然又换回来了
for(int L=1;L<=n/2;L*=2)//合并前长度
{
CalcOmega(L*2,op);
for(int j=0;j<=n-1;j+=L*2)//开头,长度=L*2
{
for(int k=0;k<=L-1;k++)
{
complex x=a[j+k];
complex y=omega[k]*a[j+L+k];
a[j+k]=x+y;
a[j+L+k]=x-y;
//蝴蝶操作
}
}
}
if(op==-1) for(int i=0;i<=n-1;i++) a[i].r=a[i].r/double(n);
}
//*******************主函数*******************
complex A[MAXN+10],B[MAXN+10],C[MAXN+10];
complex A2[MAXN+10],AB[MAXN+10],A3[MAXN+10];
double ans[MAXN+10];
int main()
{
//-------------读入-------------
int n;scanf("%d",&n);
int mx=0;
for(int i=0;i<=n-1;i++)
{
int t;scanf("%d",&t);if(t>mx) mx=t;
A[t].r=1;B[2*t].r=1;C[3*t].r=1;
}
//-------------准备-------------
int sn=1,lg=0;
while(sn<mx*3+1) sn*=2,lg++;
for(int i=0;i<=sn-1;i++) R[i]=( R[i>>1]>>1 ) | ( (i&1)<<(lg-1) );
//nlogn翻转二进制
//-------------计算-------------
for(int i=0;i<=sn-1;i++) ans[i]=(A[i].r)-(B[i].r/2.0)+(C[i].r/3.0);//先把A、B、C搞定
fft(A,sn,1);fft(B,sn,1);
for(int i=0;i<=sn-1;i++) A2[i]=A[i]*A[i],AB[i]=A[i]*B[i],A3[i]=A2[i]*A[i];
fft(A2,sn,-1);fft(AB,sn,-1);fft(A3,sn,-1);
//-------------综合-------------
for(int i=0;i<=sn-1;i++)
{
ans[i]+=(A2[i].r/2.0)+(A3[i].r/6.0)-(AB[i].r/2.0);
int t2=ans[i]+0.5;
if(t2>0) printf("%d %d\n",i,t2);
}
//ans[i]=A[i]+(A2[i]-B[i])/2+(A3[i]-3*AB[i]+2*C[i])/6
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2017-12/Triple.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%