「bzoj3028」食物 - 普通型生成函数

题目大意

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

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

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

---

题目分析

普通型生成函数系数表示与闭形式之间的转化。
学习笔记传送门。

用bool数组构造生成函数。

汉堡：$(1,1,0,0,0,0,\ldots)\Leftrightarrow 1+x\quad$(只能带$0$或$1$个)
巧克力：$(1,0,0,0,0,1,0,0,\ldots) \Leftrightarrow \frac{1}{1-x^5}\quad$($5$的倍数)
矿泉水：$(1,1,1,1,1,0,0,\ldots> \Leftrightarrow \frac{1-x^5}{1-x}\quad$(最多$4$瓶)
薯片：$(1,0,1,0,1,\ldots) \Leftrightarrow \frac{1}{1-x^2}\quad$(偶数个)
牛奶：$(1,1,1,1,0,0,\ldots) \Leftrightarrow \frac{1-x^4}{1-x}\quad$(最多$3$罐)
糖果：$(1,0,0,0,1,0,\ldots) \Leftrightarrow \frac{1}{1-x^4}\quad$($4$的倍数)

将以上闭形式全部相乘得到答案的生成函数

$$\frac{1}{(1-x)^3}\Leftrightarrow\sum_{i=0}^{+\infty}\binom{i+2}{3}x^i$$

故答案即为$\binom{n+2}{3}$。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

const int mod=10007,inv6=1668;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=(num*10+x-'0')%mod;
		x=getchar();
	}
	return num*bj;
}

int main() {
	int n=Get_Int();
	printf("%d\n",n*(n+1)%mod*(n+2)%mod*inv6%mod);
	return 0;
}