BZOJ 3028 食物

发布于 2017-04-27  184 次阅读


题目链接: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}\) 

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

 


一个非常弱的准退役OIER