over 2 years ago

前言

表示考试前根本不熟悉指数型生成函数这套理论呀,愉快暴力分。。。

题目描述

符兰省月亮中学的大土豪tty最近花1兆美刀购买了一只野生机器猫,tty最喜欢干的事情就是在机器猫的口袋中拿巧克力吃,众所周知,机器猫口袋中的巧克力是拿不完的,假设其中只有种颜色的巧克力,每次tty从中拿出一颗巧克力,其颜色等概率为中的一种。现在tty从机器猫口袋中拿出了颗巧克力放在桌子上,由于tty很基,所以他只吃那些个数是奇数的颜色的巧克力,现在他想知道恰好吃种颜色巧克力的概率。

分析

我们只要求出方案数这道题就做完了。
其实我们只要知道就行了,下面给出推导过程。

上面的分别代表出现奇数次和偶数次的情况, 的第项表示奇数+偶数和为的答案,因此我们的答案可以表示成:

考虑把之前的当作一个变量,然后多项式快速幂就可以求出具体的多项式了,然后观察一下可知,中的第项的贡献是,这样我们就可以求出了,然后就做完了。
chocolate.cpp

← BZOJ4197:[Noi2015]寿司晚宴 省选集训:4.4 →
 
comments powered by Disqus