一个非常基础（甚至不需要）的生成函数题？

感觉生成函数这种神通广大， 名字吓人的东西， 能够有这么平易近人的入门题， 对我这种弱鸡真是太友善了。

传送门

一些物品， 分别可以购买奇数个， 偶数个， 三的倍数个， 四的倍数个，0个（两种）， 0个， 0个。

问凑出(n)个物品的方案数。

解题报告

算法一

把{奇数个，0个}, {偶数个，0个}，{三的倍数个，0}, {四的倍数个， 0} 这四类拆开看， 可以发现除了第一类必须占(>=1)个物品外， 其他类组成任意个物品的方案数都是唯一的。

所以答案是将(n-1)个物品分成(4)分， 每一份可以为0的方案数， 也就是({n+2} choose{3}).

算法二

化一发生成函数： [
begin{aligned}
&F(odd)=x+x^3+x^5+...=frac{x}{1-x^2}\
&F(even)=1+x^2+x^4+...=frac{1}{1-x^2}\
&F^2(0|1)=(1+x)^2\
&F(0|1|2)=1+x+x^2=frac{1-x^3}{1-x}\
&F(0|1|2|3)=1+x+x^2+x^3=frac{1-x^4}{1-x}
end{aligned}
] 乘起来得到

[F(text{all}) = frac{x}{(1-x)^4}]

再展开得到：

[F(text{all})=x*left(1+{1+4-1choose 4-1}x+{2+4-1 choose 4-1}x^2+...right)]

答案是(x^n)项的系数， 也就是({n-1+4-1 choose 4-1}).

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

using namespace std; 
#define rep(i,a,b) for(int i=int(a),nn=int(a);i<=nn;++i) 
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i) 
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i) 
const int p=10007;
int () {
  	long long as=0; char c=getchar();
	for (;c>='0'&&c<='9'; c=getchar())as=(as*10+c-48)%p;
	as=as*(as+1)*(as+2)/1/2/3%p; 
  	return cout<<as<<endl,0; 
}