BZOJ3771 - Triple

BZOJ3771 - Click Here

  

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为方案数。

  

Solution

  故事好有趣233。

  

  显然生成函数

  根据题意易构造出下列生成函数

  $F(x) \, \leftrightarrow \, \langle a_1,a_2,..,a_n \rangle$

  $G(x) \, \leftrightarrow \, \langle 2a_1,2a_2,…,2a_n \rangle$

  $H(x) \, \leftrightarrow \, \langle 3a_1,3a_2,…,3a_n \rangle$

  

  然后来考虑一下答案。

  取1把斧头,显然为$F(x)$。

  取2把斧头,由于不能出现$(a,a)$的方案,简单容斥可得$\frac{F^2(x)-G(x)}{2!}$

  取3把斧头,由于不能出现$(a,a,a,)(a,a,b)$的情况,因此拆开多项式容斥可得$\frac{F^3(x)-3F(x)G(x)+2H(x)}{3!}$

  

  然后用FFT加速就好了~

  

CODE

CODE - Click Here

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang