BZOJ 3771 Triple

发布于 2017-08-06  250 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3771

题意: 因为很好玩就全文搬运了

我们讲一个悲伤的故事。
从前有一个贫穷的樵夫在河边砍柴。
这时候河里出现了一个水神,夺过了他的斧头,说:
“这把斧头,是不是你的?”
樵夫一看:“是啊是啊!”
水神把斧头扔在一边,又拿起一个东西问:
“这把斧头,是不是你的?”
樵夫看不清楚,但又怕真的是自己的斧头,只好又答:“是啊是啊!”
水神又把手上的东西扔在一边,拿起第三个东西问:
“这把斧头,是不是你的?”
樵夫还是看不清楚,但是他觉得再这样下去他就没法砍柴了。
于是他又一次答:“是啊是啊!真的是!”
水神看着他,哈哈大笑道:
“你看看你现在的样子,真是丑陋!”
之后就消失了。
 
樵夫觉得很坑爹,他今天不仅没有砍到柴,还丢了一把斧头给那个水神。
于是他准备回家换一把斧头。
回家之后他才发现真正坑爹的事情才刚开始。
水神拿着的的确是他的斧头。
但是不一定是他拿出去的那把,还有可能是水神不知道怎么偷偷从他家里拿走的。
换句话说,水神可能拿走了他的一把,两把或者三把斧头。
 
樵夫觉得今天真是倒霉透了,但不管怎么样日子还得过。
他想统计他的损失。
樵夫的每一把斧头都有一个价值,不同斧头的价值不同。总损失就是丢掉的斧头价值和。
他想对于每个可能的总损失,计算有几种可能的方案。
注意:如果水神拿走了两把斧头 a 和 b,(a,b) 和 (b,a) 视为一种方案。拿走三把斧头时,(a,b,c),(b,c,a),(c,a,b),(c,b,a),(b,a,c),(a,c,b) 视为一种方案。

这种需要记录方案的题,适合考虑母函数。
其中,母函数表现为一个多项式的系数表达式的形式。若 i 次项有系数,则可以得到值 i。
另外,对于确定的系数,也可以表示构成该方案的方案数。
我们记多项式\(A\) 表示拿走一把斧头的母函数:
这样,一个朴素的统计答案的方法就是:\(ans=A+A^2+A^3\)
显然这是错的,考虑错在哪里了:
首先,对于改变顺序后的选择,是同样的,所以对于 i 把斧头的情况,应该除以\(i!\)
那么\(ans=\frac{A}{1!}+\frac{A^2}{2!}+\frac{A^3}{3!}\)
然而这仍然是错的... 考虑还有哪里没考虑到:
这种统计方式中,包含了一把斧头拿超过一次的情况,所以考虑单独减去它们。
可以通过构造多项式\(B\) 表示强制拿走一把斧头两次的母函数,\(C\) 表示强制拿走一把斧头三次的母函数。
对于原 ans 式的三项,手动容斥考虑,第一项无须改动,第二项显然应该改为\(\frac{A^2-B}{2}\),直接减掉即可
第三项是稍复杂的:首先减去两把重复的情况 \(A*B\),但是考虑到,两把重复的情况是会在三种情况下被统计到的(形如\((y,x,x),(x,y,x),(x,x,y)\)),所以应该减去三倍
但是两把重复的情况包含了三把重复的情况,三把重复的情况只需减去两次即可,所以加回来两次。
所以第三项为\(\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}\)
母函数的次数很大,需要 fft 加速计算

 


一个非常弱的准退役OIER