隐藏
「bzoj3028」食物 - 普通型生成函数 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「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$的倍数)

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

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


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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;
}
姥爷们赏瓶冰阔落吧~