首先我们有一些函数推收敛式的套路。比如对于 $y=1+x+x^2$ ,我们知道 $xy=x+x^2+x^3$,所以有 $xy-x^3=y-1$,即 $y=\frac{1-x^3}{1-x}$。用类似的方法,我们还可以知道 $\sum_{i=0}^{inf}=\frac{1}{1-x}$等。

然后我们写一下所有食物的生成函数:
汉堡:$\sum_{i=0}^{inf} x^{2i} =\frac{1}{1-x^2}$
可乐:$1+x$
鸡腿:$1+x+x^2=\frac{1-x^3}{1-x}$
蜜桃多:$\sum_{i=0}^{inf} x^i -\sum_{i=0}^{inf} x^{2i}=\frac{x}{1-x^2}$
鸡块:$\sum_{i=0}^{inf} x^{4i}=\frac{1}{1-x^4}$
包子:$1+x+x^2+x^3=\frac{1-x^4}{1-x}$
土豆:$1+x$
面包:$\sum_{i=0}^{inf}x^{3i}=\frac{1}{1-x^3}$

把它们全部乘起来得:$\frac{x}{(1-x)^4}$,在这个多项式中,$n$次项的系数就是选 $n$个食物的方案数。
将 $(1-x)^{-4}$展开。我们知道 $k$次项的系数为 $(-1)^k(^k_{-4})$ ,而
$$( _ n^k) = \frac{\prod _ {i=0}^{k-1} (n-i)}{k!}$$
所以 $(1-x)^{-4}$的 $n$次项系数为 $\frac{(n+1)(n+2)(n+3)}{6}$。又因为原多项式还要乘以一个 $x$,所以它的 $n$次项系数,也就是答案,就是 $\frac{n(n+1)(n+2)}{6}$
然后边读入边取模什么的一下子就搞出来了。

分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注