题目链接：LOJ 3106
大中锋的学院要组织学生参观博物馆，要求学生们在博物馆中排成一队进行参观。
他的同学可以分为四类：一部分最喜欢唱、一部分最喜欢跳、一部分最喜欢 rap，还有一部分最喜欢篮球。如果队列中 $k, k + 1, k + 2, k + 3$ 位置上的同学依次，最喜欢唱、最喜欢跳、最喜欢 rap、最喜欢篮球，那么他们就会聚在一起讨论蔡徐坤。
大中锋不希望这种事情发生，因为这会使得队伍显得很乱。
大中锋想知道有多少种排队的方法，不会有学生聚在一起讨论蔡徐坤。两个学生队伍被认为是不同的，当且仅当两个队伍中至少有一个位置上的学生的喜好不同。
由于合法的队伍可能会有很多种，种类数对 $998244353$ 取模。
数据范围：$1 \le n \le 1000$，$0 \le a, b, c, d \le 500$，$a + b + c + d \ge n$。
题目链接：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
阿狸的国家有 $n$ 个城市，现在国家需要在某些城市对之间建立一些贸易路线，使得整个国家的任意两个城市都直接或间接的连通。
为了省钱，每两个城市之间最多只能有一条直接的贸易路径。对于两个建立路线的方案，如果存在一个城市对，在两个方案中是否建立路线不一样，那么这两个方案就是不同的，否则就是相同的。现在你需要求出一共有多少不同的方案。
换句话说，你需要求出 $n$ 个点的简单（无重边无自环）无向连通图数目。由于这个数字可能非常大，你只需要输出方案数对 $1004535809 = 479 \times 2 ^ {21} + 1$ 取模的值即可。
数据范围：$1 \le n \le 1.3 \times 10 ^ 5$。
题目链接：SPOJ 16607
John 有 $n$ 个水果罐子，每个罐子都装有不同种类的糖果，第 $i$ 个罐子里有 $m_i$ 个糖果。John 决定吃一些糖果，并且打算至少吃 $a$ 个，至多吃 $b$ 个，求一共有多少种吃法。答案对 $2004$ 取模。
数据范围：$1 \le n \le 10$，$0 \le a \le b \le 10 ^ 7$，$0 \le m_i \le 10 ^ 7$。
题目链接：Codeforces 1186F
Vus 有一张包含 $n$ 个点和 $m$ 条边的图。设 $d_i$ 表示第 $i$ 个点的度数。他需要保留 $\left\lceil\frac{n + m}{2}\right\rceil$ 条边，设 $f_i$ 表示新图中第 $i$ 个点的度数。他需要对于所有的 $i$ 保证 $\left\lceil\frac{d_i}{2}\right\rceil \le f_i$。
请你帮 Vus 保留一些边使这张图满足条件。
数据范围：$1 \le n \le 10 ^ 6$，$0 \le m \le 10 ^ 6$。
题目链接：Codeforces 1186E
Vus 有一个 $n \times m$ 的 $01$ 矩阵，他通过如下方法构造了一个无限大的矩阵：
我们将列从上到下标号为 $1$ 到 $\infty$，将行从左到右标号为 $1$ 到 $\infty$。接下来进行 $q$ 次询问，每次询问子矩阵 $(x_1, y_1, x_2, y_2)$ 的元素之和。
数据范围：$1 \le n, m \le 1000$，$1 \le q \le 10 ^ 5$，$1 \le x_1 \le x_2 \le 10 ^ 9$，$1 \le y_1 \le y_2 \le 10 ^ 9$。
题目链接：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
我们的小朋友很喜欢计算机科学，尤其喜欢二叉树。
考虑一个含有 $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$。
题目链接：Codeforces 1185F
有 $n$ 个人想要买两个比萨。众所周知，比萨共有 $9$ 种成分，用 $1$ 到 $9$ 的整数表示。每个人都有若干喜欢的成分（至多有 $9$ 种）；商店里一共有 $m$ 个比萨，每个比萨都有若干成分组成和一个价格 $c_i$。
你需要选择 $2$ 个比萨，使这些人中满足的人数最多。如果一个人是满足的当且仅当对于任何一个他喜欢的成分，至少出现在其中一个比萨中。如果有多种方案，输出价格最小的方案。
数据范围：$1 \le n \le 10 ^ 5$，$2 \le m \le 10 ^ 5$，$1 \le c_i \le 10 ^ 9$。
题目链接：Codeforces 1180D
你有一个 $n \times m$ 的网格图，最初你在 $(1, 1)$ 的位置。每次你需要选择一个 $(dx, dy)$，从当前位置 $(x, y)$ 移动到 $(x + dx, y + dy)$ 的位置。显然你不能离开网格，而且你必须将每个格子访问恰好一次（最初的 $(1, 1)$ 被认为是已经访问过了），所使用的 $(dx, dy)$ 还需要保证两两不同。
数据范围：$1 \le n \cdot m \le 10 ^ 6$。