一个非常基础(甚至不需要)的生成函数题?

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

传送门

题目大意

一些物品, 分别可以购买奇数个, 偶数个, 三的倍数个, 四的倍数个,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-1\choose 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
#include <bits/stdc++.h>
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 main() {
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;
}

留言