给出一个长度为 $n$ 仅包含小写字符的字符串 $s$。

定义后缀 $i$ 的权值为 $w_i$，定义两个不同后缀 $i, j(i \neq j)$ 的贡献为 $\mathrm{LCP}(i, j) + (w_i \operatorname{xor} w_j)$。其中 $\mathrm{LCP}(i, j)$ 表示后缀 $i$ 和后缀 $j$ 的最长公共前缀长度。

你需要求出任意两个不同后缀 $i, j(i \neq j)$ 的贡献最大值。

数据范围：$1 \leq n \leq 10^5$，$0 \leq w_i < n$。

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

给出一个包含 $n$ 个字符串的集合 $D$ 以及一个字符串 $s$，你需要找出集合 $D$ 中字典序小于 $s$ 的字符串数量。

字符串 $s$ 会经过 $Q$ 次修改，每次修改会给出一个整数 $k$ 以及一个字符 $c$，表示将字符串 $s$ 从第 $k$ 个字符开始到字符串末尾的所有字符替换成 $c$。每次修改完字符串 $s$ 之后，你都需要求出集合 $D$ 中字典序小于 $s$ 的字符串数量。

数据范围：$1 \leq n, Q \leq 10^6$，$1 \leq |s| \leq 10^6$，字符串集合 $D$ 的总长不超过 $10^6$。

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

给出一棵大小为 $n$ 的树。

对于每个 $k$ ($0 \leq k \leq n - 1$)，你需要求出有多少个大小为 $n$ 的带标号树与原树有恰好 $k$ 条重合的边。答案对 $10^9 + 7$ 取模。

数据范围：$1 \leq n \leq 100$。

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

给出一棵包含 $n$ 个节点的树。你需要给每个节点染上数字 $0$ 或 $1$。

路径 $(u, v)$ 的权值，等于从 $u$ 到 $v$ 的最短路径上所有节点数字的 MEX。一种染色方案的权值等于所有 $1 \leq u \leq v \leq n$ 的路径 $(u, v)$ 的权值之和。

请求出所有的染色方案中，可能的最大权值。

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

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

给出一张包含 $n$ 个点 $m$ 条边的无向图，每个点有一个颜色 $c_i$ ($1 \leq c_i \leq k$)，求有多少组颜色对 $a, b$ ($a < b$) 满足保留颜色为 $a$ 或 $b$ 的节点的导出子图是二分图。

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

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

给出一个长度为 $n$ 的数组 $a$，你需要找出字典序最大的子序列 $s$，使得 $s$ 可以作为多边形的边长。

当且仅当 $|s| \geq 3$ 且满足以下条件时，$s$ 可以作为多边形的边长

$$2 \cdot \max(s_1, \cdots, s_{|s|}) < s_1 + \cdots + s_{|s|}$$

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

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

给出一棵包含 $n$ 个点的树，编号 $1 \sim n$。第 $i$ 个点的高度为 $h_i$。

你可以在任意点放置任意数量的塔，对于每个塔，你可以选择放在哪个点，并且可以选择它的效率。设置一个效率为 $e$ 的塔需要花费 $e$ 金币，其中 $e > 0$。

如果存在一对分别位于 $u, v$ ($u \neq v$) 的信号塔，它们的效率分别为 $e_u, e_v$，且满足 $\min(e_u, e_v) \geq h_x$，且点 $x$ 位于从 $u$ 到 $v$ 的路径上，则我们认为 $x$ 能够收到信号。

请你求出使得所有顶点都接收到信号，所需的最小金币数。

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

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

给出一个长度为 $n$ 的序列 $a$，仅由 $0$ 或 $1$ 构成。

你需要对序列进行至多 $n$ 次操作（或者说明这是不可能的），每次操作你可以选择一个下标 $i$ ($1 \leq i \leq n - 2$)，然后将 $a_i, a_{i + 1}, a_{i + 2}$ 均改成 $a_i \oplus a_{i + 1} \oplus a_{i + 2}$。

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

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

有 $p$ 个人玩一个游戏，第 $i$ 个人的得分为 $a_i$。

已知 $\sum a_i = s$ 且 $a_1 \geq r$，得分最高的人可以获胜，若多个人得分最高，则等概率随机其中一个人获胜。

求第一个人获胜的概率，答案对 $998244353$ 取模。

数据范围：$1 \leq p \leq 100$，$0 \leq r \leq s \leq 5000$。

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