生成函数
$ g(x)=a_0+a_1x+a_2x^2+...+a_nx^n(-1 \leq x \leq 1) $
P10780 BZOJ3028 食物
题目描述
明明这次又要出去旅游了，和上次不同的是，他这次要去宇宙探险！我们暂且不讨论他有多么 NC，他又幻想了他应该带一些什么东西。理所当然的，你当然要帮他计算携带 件物品的方案数。
他这次又准备带一些受欢迎的食物，如：蜜桃多啦，鸡块啦，承德汉堡等等。
当然，他又有一些稀奇古怪的限制：
每种食物的限制如下：
- 承德汉堡：偶数个；
- 可乐： 个或 个；
- 鸡腿： 个， 个或 个；
- 蜜桃多：奇数个；
- 鸡块： 的倍数个；
- 包子： 个， 个， 个或 个；
- 土豆片炒肉：不超过一个；
- 面包： 的倍数个；
注意，这里我们懒得考虑明明对于带的食物该怎么搭配着吃，也认为每种食物都是以『个』为单位（反正是幻想嘛），只要总数加起来是 就算一种方案。因此，对于给出的 ，你需要计算出方案数，并对 取模。
提示
- 对于 的数据，但是 ；
- 对于所有数据，；
思路
- 承德汉堡的生成函数：$ 1+x^2+x^4+...+x^n=\frac{1}{1-x^2} $
- 可乐为：$ 1+x=\frac{1-x^2}{1-x} $
- 鸡腿为：$ 1+x+x^2=\frac{1-x^3}{1-x} $
- 蜜桃为：$ x+x^3+x^5+...+x^n=\frac{x}{1-x^2} $
- 鸡块为：$ 1+x^4+x^8+...x^n=\frac{1}{1-x^4} $
- 包子为：$ 1+x+x^2+x^3+x^4=\frac{1-x^4}{1-x} $
- 土豆片炒肉为：$ 1+x=\frac{1-x^2}{1-x} $
- 面包为：$ 1+x^3+x^6+...=\frac{1}{1-x^3} $
- 全部相乘得到 $ f(x)=\frac{x}{(1-x)^4} $
- 将式子展开，得到的 $ x^n $ 的系数即为方案数
- $ f(x)=x(\sum {n=0}^{∞}C^{4-1}x^n)= \sum {n=0}^{∞}C^{3}x^{n+1}$
- 答案即为 $ C_{n+2}^3=\frac{(n+2)(n+1)n}{6} $