标签 生成函数 下的文章
- 首页
- 生成函数
「Luogu 4389」付公主的背包
题目链接:Luogu 4389
付公主有一个可爱的背包,这个背包最多可以装 $10 ^ 5$ 大小的东西。付公主有 $n$ 种商品,她要准备出摊了。每种商品体积为 $V_i$,都有 $10 ^ 5$ 件。
给定 $m$,对于整数 $s \in [1, m]$,请你回答用这些商品恰好装 $s$ 体积的方案数。
数据范围:$1 \le n \le 10 ^ 5$,$1 \le V_i \le m \le 10 ^ 5$。
「Luogu 4841」城市规划
题目链接:Luogu 4841
阿狸的国家有 $n$ 个城市,现在国家需要在某些城市对之间建立一些贸易路线,使得整个国家的任意两个城市都直接或间接的连通。
为了省钱,每两个城市之间最多只能有一条直接的贸易路径。对于两个建立路线的方案,如果存在一个城市对,在两个方案中是否建立路线不一样,那么这两个方案就是不同的,否则就是相同的。现在你需要求出一共有多少不同的方案。
换句话说,你需要求出 $n$ 个点的简单(无重边无自环)无向连通图数目。由于这个数字可能非常大,你只需要输出方案数对 $1004535809 = 479 \times 2 ^ {21} + 1$ 取模的值即可。
数据范围:$1 \le n \le 1.3 \times 10 ^ 5$。
「BZOJ 2173」整数的 lqp 拆分
题目链接:BZOJ 2173
lqp 在为出题而烦恼,他完全没有头绪,好烦啊……
他首先想到了整数拆分。整数拆分是个很有趣的问题。给你一个正整数 $n$,对于 $n$ 的一个整数拆分就是满足任意 $m > 0$,$a_1, a_2, a_3, \dots, a_m > 0$,且 $a_1 + a_2 + a_3 + \dots + a_m = n$ 的一个有序集合。通过长时间的研究我们发现了计算对于 $n$ 的整数拆分的总数有一个很简单的递推式,但是因为这个递推式实在太简单了,如果出这样的题目,大家会对比赛毫无兴趣的。
然后 lqp 又想到了斐波那契数。定义:
$$ f_n = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ f_{i - 1} + f_{i - 2} & n > 1 \end{cases} $$
$f_n$ 就是斐波那契数的第 $n$ 项。但是求出第n项斐波那契数似乎也不怎么困难……lqp 为了增加选手们比赛的欲望,于是绞尽脑汁,想出了一个有趣的整数拆分,我们暂且叫它:整数的 lqp 拆分。
和一般的整数拆分一样,整数的 lqp 拆分是满足任意 $m > 0$,$a_1, a_2, a_3, \dots, a_m > 0$,且 $a_1 + a_2 + a_3 + \dots + a_m = n$ 的一个有序集合。但是整数的 lqp 拆分要求的不是拆分总数,相对更加困难一些。
对于每个拆分,lqp 定义这个拆分的权值 $\prod_{i = 1} ^ m f_{a_i}$,他想知道对于所有的拆分,他们的权值之和是多少?
由于这个数会十分大,lqp 稍稍简化了一下题目,只要输出对于 $n$ 的整数 lqp 拆分的权值和模 $10 ^ 9 + 7$ 即可。
数据范围:$1 \le n \le 10 ^ 6$。
「Codeforces 438E」The Child and Binary Tree
题目链接:Codeforces 438E
我们的小朋友很喜欢计算机科学,尤其喜欢二叉树。
考虑一个含有 $n$ 个互不相同的正整数序列 $c_1, c_2, \dots, c_n$。如果一棵带点权有根二叉树满足其所有节点的权值都属于集合 $\{c_1, c_2, \dots, c_n\}$ 中,那么小朋友就会将其称作「好的」。并且他认为,这棵二叉树的权值是所有节点的权值总和。
给出一个整数 $m$,你需要对于所有整数 $s \in [1, m]$,计算出权值为 $s$ 的「好的」二叉树数量。答案对 $998244353$ 取模。
数据范围:$1 \le n, m, c_i \le 10 ^ 5$。