给出一个包含 $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。

给出一个包含 $n$ 个点的树。

你可以进行若干次操作，每次你可以删除这棵树的一个叶子（即保证剩下部分仍然是连通的）。

你需要求出有多少种删除叶子的方案，使得剩下部分的重心唯一（这里的重心定义与平常相同，即最大子树最小的节点）。

答案对 $998244353$ 取模，两个方案不同当且仅当删除叶子节点构成的集合不同。

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

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

This is an interactive problem.

给出一个 $n$ 个点 $m$ 条边的有向无环图（DAG）。你会得到该 DAG 的结构，但不会知道 DAG 中每条边的边权。

在任意一对顶点 $s$ 与 $t$ 之间可能存在多条路径，我们将一条路径的权值定义为该路径上所有边权的乘积。记 $f(s, t, c)$ 表示从 $s$ 到 $t$ 的所有不同路径，在所有边权都乘以 $c$ 情况下的权值之和，对 $998244353$ 取模。

你可以进行至多 $999$ 次询问，每次询问你需要给出参数 $s, t, c$，交互器会返回 $f(s, t, c)$ 的值。

最后，交互器会给出一个参数 $k$，你需要确定 $f(1, n, k)$ 的值。

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

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

Alice 和 Bob 正在玩取石子游戏。

有 $n$ 个房间，第 $i$ 个房间中有 $k_i(k_i \geq 1)$ 堆石子。Alice 和 Bob 轮流操作，Alice 先手。

每次操作时，玩家必须在当前房间中，选择任意一个非空的堆，然后在该堆中取出任意一个石子。只有在当前房间中将所有石子取完，Alice 和 Bob 才可以到下一个房间继续进行游戏。若某位玩家无法进行操作（即到了最后一个房间并且房间为空），则该玩家输掉游戏。

在游戏开始前，Alice 可以决定房间的访问顺序，访问顺序可以用一个排列 $p$ 描述，表示依次经过房间 $p_1, p_2, \cdots, p_n$，只有房间 $p_i$ 没有石子的情况下，才可以去房间 $p_{i + 1}$。

假设 Alice 和 Bob 进行的都是最优决策，Alice 想知道他有多少种排列 $p$ 可以获胜。答案对 $10^9 + 7$ 取模。

数据范围：$1 \leq n \leq 10^6$，$1 \leq \sum k_i \leq 10^6$，石子数量 $\in [1, 10^9]$。

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