BZOJ 3028 食物


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

题意:有几种食物,每种的选取都有某种限制,问取 n 个食物的方案数有多少....


母函数练习题,对每一个限制均生成一个母函数,将这些母函数卷积在一起即可。具体如下:

$$汉堡:1+x^{2}+x^{4}+...=\frac{1}{1-x^{2}}$$

$$可乐:1+x$$

$$鸡腿:1+x+x^{2}=\frac{1-x^{3}}{1-x}$$

$$蜜桃多:x+x^{3}+x^{5}...=\frac{x}{1-x^{2}}$$

$$鸡块:1+x^{4}+x^{8}+...=\frac{1}{1-x^{4}}$$

$$包子:1+x+x^{2}+x^{3}=(1+x)(1+x^{2})$$

$$土豆片炒肉:1+x$$

$$面包:1+x^{3}+x^{6}+...=\frac{1}{1-x^{3}}$$

卷起来后化简结果为:$$f_(x)=\frac{x}{(1-x)^{4}}$$

此时可以使用泰勒公式进行复杂的暴力求解... 然而我们进一步变形....

$$f_(x)=x(1+x+x^{2}+x^{3}+...)^4$$

然后应用多项式定理,xn 的系数就是一个简单的组合数问题啦

但是要注意的是... 式子前面有一个 x,所以 n 要减一计算... 结果即为\(C_{n+2}^{3}\) 

然后预处理出逆元即可,代码如下:

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 3028 食物


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , , ,