标签 生成函数 下的文章

「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$。