发布时间：2024-09-29

生成函数

概念

$g(x)=a_0+a_1x+a_2x^2+...+a_nx^n(-1 \leq x \leq 1)$

P10780 BZOJ3028 食物

题目描述

明明这次又要出去旅游了，和上次不同的是，他这次要去宇宙探险！我们暂且不讨论他有多么 NC，他又幻想了他应该带一些什么东西。理所当然的，你当然要帮他计算携带 $n$ 件物品的方案数。

他这次又准备带一些受欢迎的食物，如：蜜桃多啦，鸡块啦，承德汉堡等等。

当然，他又有一些稀奇古怪的限制：

每种食物的限制如下：

• 承德汉堡：偶数个；
• 可乐：$0$ 个或 $1$ 个；
• 鸡腿：$0$ 个，$1$ 个或 $2$ 个；
• 蜜桃多：奇数个；
• 鸡块：$4$ 的倍数个；
• 包子：$0$ 个，$1$ 个，$2$ 个或 $3$ 个；
• 土豆片炒肉：不超过一个；
• 面包：$3$ 的倍数个；

注意，这里我们懒得考虑明明对于带的食物该怎么搭配着吃，也认为每种食物都是以『个』为单位（反正是幻想嘛），只要总数加起来是 $n$ 就算一种方案。因此，对于给出的 $n$，你需要计算出方案数，并对 $10007$ 取模。

提示

• 对于 $40\%$ 的数据，但是 $1\leq n\leq 10^5$；
• 对于所有数据，$1\leq n\leq 10^{500}$；

思路

• 承德汉堡的生成函数：$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_{n+4-1}^{4-1}x^n)= \sum _{n=0}^{∞}C_{n+3}^{3}x^{n+1}$
• 答案即为 $C_{n+2}^3=\frac{(n+2)(n+1)n}{6}$