BZOJ3028 - 食物

2017-12-28 数学相关 Viewed times

Description

　　明明这次又要出去旅游了，和上次不同的是，他这次要去宇宙探险！我们暂且不讨论他有多么NC，他又幻想了他应该带一些什么东西。理所当然的，你当然要帮他计算携带N件物品的方案数。他这次又准备带一些受欢迎的食物，如：蜜桃多啦，鸡块啦，承德汉堡等等当然，他又有一些稀奇古怪的限制：每种食物的限制如下：

　　承德汉堡：偶数个

　　可乐：0个或1个

　　鸡腿：0个，1个或2个

　　蜜桃多：奇数个

　　鸡块：4的倍数个

　　包子：0个，1个，2个或3个

　　土豆片炒肉：不超过一个

　　面包：3的倍数个

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

　　输入一个数字N，1<=n<=10^500

　　如题

　　显然可得答案$\binom{n+2}{3}$，毫无思维难度！

　　……开玩笑的……怎么可能……

　　根据题意，可以构造出每个物品的生成函数。

　　承德汉堡：$\sum_{0 \leq k} x^{2k} = \frac{1}{1-x^2}$

　　可乐：$1+x$

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

　　蜜桃多：$\sum_{0 \leq k} x^{2k+1} = \frac{x}{1-x^2}$

　　鸡块：$\sum_{0 \leq k} x^{4k} = \frac{1}{1-x^4}$

　　包子：$1+x+x^2+x^3=\frac{1-x^4}{1-x}$

　　土豆片炒肉：$1+x$

　　面包：$\sum_{0 \leq k} x^{3k} = \frac{1}{1-x^3}$

　　把上面全部乘起来就得到答案的生成函数$F(x)=\frac{x}{(1-x)^4}$

　　题目要求的答案就是$[x^n]F(x)$，因此只需要展开$F(x)$即可求解。

　　至于如何展开，这里提供两种方法。

　　(1)二项展开式

　　$F(x)=x \cdot (1-x)^{-4}$，$(1-x)^{-4}$可以利用二项展开式得到$\sum \binom{-4}{k} \cdot (-1)^{k} \cdot x^k$

　　因此$F(x)=\sum \binom{-4}{k}x^{k+1}$，此时$[x^n]F(x) = \binom{-4}{n-1} \cdot (-1)^{n-1}$

　　对上指标变换一下，得到$[x^n]F(x) = \binom{n+2}{n-1} = \binom{n+2}{3}$

　　(2)泰勒展开式

　　可以直接对$F(x)$关于$x=0$泰勒展开(即麦克劳林公式)，此时得到$[x^n]F(x)=\frac{F^{(n)}(x)}{n!}$

　　因此现在的问题是求出$F(x)$的$n$阶导数。

　　首先定义$G(x)=x , \, H(x)=(1-x)^{-4}$，则$F(x)=G(x)H(x)$

　　根据莱布尼茨公式可得$F^{(n)}(x) = \sum_{i=0}^n \binom{n}{i}G^{(i)}(x) \cdot H^{(n-i)}(x)$

　　又由于当$i>1$时，$G^{(i)}(x)=0$。因此可得$F^{(n)}(x)=xH^{(n)}(x)+nH^{(n-1)}(x)$

　　即$F^{(n)}(x) = \frac{(n+3)!}{3!}x(1-x)^{-4-n} + \frac{(n+2)!}{3!}n(1-x)^{-n-3}$

　　将上式带入$\frac{F^{(n)}(0)}{n!}$就得到了$\binom{n+2}{3}$

　　然后，下指标那么小，直接求出乘法逆元计算就好了。