给出一个关于 $n$ 的排列 $a$，对排列 $a$ 使用 Fast Bogosort：

• 如果数组已经有序，则算法终止。
• 否则，将数组划分成尽可能多的区间，每个区间 $[l, r]$ 恰好包含 $[l, r]$ 中的所有数字。注意区间不能重叠，并且他们的并集为 $[1, n]$。
• 对于每个被划分的区间 $[l, r]$，如果 $l < r$，则调用 shuffle(l, r)，在区间 $[l, r]$ 内均匀随机打乱数字。

现在，请你计算对排列 $a$ 使用 Fast Bogosort，shuffle 函数的期望调用次数。

数据范围：$1 \leq n \leq 10^5$。

时空限制：$3$s / $1024$MiB。

给出一个非负整数序列 $a_1, a_2, \cdots, a_n$。初始时，你可以创造一个机器人，高度为 $[0, d]$ 之间的正整数。每当经过一个检查点 $a_i$ 时，如果当前的高度 $h$ 满足 $h \geq a_i$，则高度 $h \gets h - a_i$；否则不会发生任何事。

有 $Q$ 次询问，每次询问给出两个正整数 $l, r(1 \leq l \leq r \leq n)$，你需要选择机器人的初始高度，使得依次经过检查点 $a_l, \cdots, a_r$ 之后机器人剩下的高度最大，你只需要求出该高度即可。

数据范围：$1 \leq n, Q \leq 3 \times 10^5$，$1 \leq d \leq 10^9$，$0 \leq a_i \leq 10^9$，$1 \leq l \leq r \leq n$。

时空限制：$1$s / $256$MiB。

有 $n$ 个人，分别位于坐标轴上的 $p_1, \cdots, p_n$ 位置。初始时 $p_i = i$。

你可以在坐标轴上的某个位置 $x(1 \leq x \leq n)$ 放置一个景点，接下来所有人都会朝着这个景点靠拢。具体地，对于每个人 $i$：

• 若 $p_i = x$，则位置不变。
• 若 $p_i < x$，则向右走一步 $p_i \gets p_i + 1$。
• 若 $p_i > x$，则向左走一步 $p_i \gets p_i - 1$。

每个位置 $x$ 都有一个对应的权值 $a_x$，对于某一时刻的站位数组 $p_1, \cdots, p_n$，得分定义为

$$\sum_{i = 1}^n a_{p_i}$$

你可以进行任意次操作，每次放置景点的位置任选。对于所有可能的站位数组 $p$，你需要求出得分总和。答案对 $998244353$ 取模。

数据范围：$1 \leq n \leq 2 \times 10^5$，$1 \leq a_i \leq 10^9$。

时空限制：$2$s / $256$MiB。

给出一个包含 $n$ 个点的完全图，节点编号为 $1 \sim n$，其中 $i, j(i \neq j)$ 之间的边权为 $a_{i + j}$，求这张图的最小生成树。

数据范围：$2 \leq n \leq 2 \times 10^5$，$1 \leq a_i \leq 10^9$。

时空限制：$3$s / $256$MiB。

给出一个正整数 $n$ 和一个整数 $P \in [0, 100]$，记 $p = \frac{P}{100}$。

有一个正整数序列 $a$。初始时，$a$ 的长度为 $1$，且 $a_1 = 1$。

接下来会对 $a$ 进行操作 $n - 1$ 次。每次操作，有 $p$ 的概率执行操作 1，有 $1 - p$ 的概率执行操作 2。记 $m$ 是不出现在 $a$ 中的最小正整数。

• 操作 1：将 $m$ 添加到序列 $a$ 的末尾。
• 操作 2：记 $c_1, \cdots, c_{m - 1}$ 分别表示 $1, \cdots, m - 1$ 在 $a$ 中的出现次数。在 $1, \cdots, m - 1$ 中按照与 $c_k$ 成正比的概率选择一个数 $k$（即概率为 $c_k / \sum_{j = 1}^{m - 1} c_j$）。然后将 $k$ 添加到序列 $a$ 的末尾。

请你求出 $1, \cdots, n$ 在操作结束后在 $a$ 中的期望出现次数。答案对 $998244353$ 取模。

给出一个正整数 $n$。

对于一个长度为 $n$ 的整数序列 $A = \{a_1, a_2, \cdots, a_n\}$，设 $f(A)$ 表示 $a_1 \sim a_n$ 顺次连接构成的十进制数值 $\overline{a_1\cdots a_n}$。例如 $f(\{ 1, 20, 34 \}) = 12034$。

你需要对于 $n$ 的所有排列 $P$，求出 $f(P)$ 之和。答案对 $998244353$ 取模。

数据范围：$1 \leq n \leq 2 \times 10^5$。

时空限制：$2$s / $1024$MiB。

有 $n$ 枚 $m + 1$ 面的骰子，$m + 1$ 个面上分别写着 $0 \sim m$，丢出第 $i$ 枚骰子使得数字 $j$ 朝上的概率永远是 $p_{i, j}$。

你打算投 $Q$ 轮骰子，第 $i$ 次你会将编号在 $[l_i, r_i]$ 中的骰子全部掷出，将每个骰子面朝上的数字相加，设总和是 $\mathrm{sum}$，若 $\mathrm{sum} \leq m$，你会获得 $b_{\mathrm{sum}}$ 的开心度，否则你将什么都得不到。

请你求出每一轮投骰子，得到的开心度的期望是多少。答案对 $10^9 + 7$ 取模。

数据范围：$1 \leq n \leq 1500$，$1 \leq m \leq 200$，$1 \leq Q \leq 6 \times 10^5$。

时空限制：未知。

有 $n$ 名玩家进行游戏，每个玩家都有一个初始能力值 $a_i$。

游戏会进行 $t$ 轮，每一轮会等概率随机选择两个不同的人，将他们的能力值分别加 $1$。

求游戏结束后，$\sum\limits_{1 \leq i < j \leq n} [a_i = a_j]$ 的期望值。答案对 $998244353$ 取模。

数据范围：$2 \leq n \leq 10^6$，$1 \leq t \leq 10^7$，$1 \leq a_i \leq 10^6$。

时空限制：$6$s / $512$MiB。

有 $n$ 种物品，其中第 $i$ 种物品的体积为 $v_i$，每一种物品的数量都是无限的。

给出背包的体积上限 $m$，对于 $s \in [1, m]$，你都需要求出使用这些物品恰好装满 $s$ 体积的方案数。两个方案不同当且仅当存在某个物品的选取个数不同。

数据范围：$1 \leq n, m \leq 10^5$，$1 \leq v_i \leq m$。

时空限制：$1$s / $500$MiB。

给出一个长度为 $n$ 的序列 $a_0, a_1, \cdots, a_{n - 1}$，保证 $n$ 是 $2$ 的若干次幂。

有 $Q$ 次操作，每次操作都形如以下操作中的一种：

• 1 l r k：对于所有 $i \in [l, r)$，令 $b_i = a_{i \oplus k}$。然后对于所有 $i \in [l, r)$，令 $a_i = b_i$。
• 2 l r：求 $\sum_{i = l}^{r - 1} a_i$ 的值。

其中 $\oplus$ 表示按位异或。

数据范围：$1 \leq n \leq 2^{18}$，保证 $n$ 是 $2$ 的若干次幂，$1 \leq Q \leq 2 \times 10^5$，$1 \leq a_i \leq 1048576$，$0 \leq l < r \leq n$，$0 \leq k < n$。

时空限制：$2$s / $64$MiB。