已知一个字符串 $S$ 的长度为 $n$，字符集大小为 $m$。现在均匀随机地生成该字符串 $S$。

记随机变量 $X$ 表示该字符串 $S$ 中回文子串的数量，求 $E(X^2)$。答案对给定质数 $p$ 取模。

数据范围：$1 \leq n \leq 2 \times 10^5$，$1 \leq m \leq 10^7$，$m < p < 10^9$。

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

给出一个包含 $n$ 个点 $m$ 条边的带权无向图。

你需要找出 $n - 1$ 条边，使得这些边的权值之和最小，且不构成一棵树。

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

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

给出一个长度为 $n$ 的非递增序列 $a_1, a_2, \cdots, a_n$（满足 $a_1 \geq a_2 \geq \cdots \geq a_n$）。

有 $Q$ 次查询，每次查询给出 $l, r, x$，你会依次遍历 $a_l, a_{l + 1}, \cdots, a_r$，你有一个计数器 $s$（初始 $s = 0$），每次将当前遍历到的数累加进 $s$，若任意时刻 $s \geq x$，你就会将 $s$ 清零。你需要求出遍历结束时，将 $s$ 清零的次数以及最后 $s$ 的值。

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

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

有 $T$ 组数据，每组数据给出 $f, x, g, y, n, m$，你需要求出

$$\sum_{i = 0}^{n - 1} \left[ (fi + x) \bmod m < (gi + y) \bmod m \right]$$

数据范围：$1 \leq T \leq 10^4$，$1 \leq f, x, g, y, n, m \leq 10^6$。

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

给出一棵包含 $n$ 个节点的树，边带权。

有 $Q$ 次询问，每次询问给出 $k$ 个区间 $[l_1, r_1], \cdots, [l_k, r_k]$，定义点集 $V$ 表示至少被一个区间包含的点构成的集合。

考虑 $V$ 的所有无序点对 $(u, v)$，将树上 $u, v$ 之间的简单路径上所有边进行染色。你需要求出所有被染色边的最大边权。

数据范围：$1 \leq n, Q\leq 2 \times 10^5$，$1 \leq \sum k \leq 2 \times 10^5$，$1 \leq l_i \leq r_i \leq n$。

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

已知三个整数 $a, b, c$。定义 $F_n(x) = (ax^2 + bx + c)^n$。

有 $Q$ 次询问，每次询问给出两个参数 $n, k$，你需要求出 $\sum_{i = 0}^k[x^i]F_n(x)$。答案对 $10^9 + 7$ 取模。

本题强制在线。

数据范围：$1 \leq a, b, c \leq 10^9 + 6$，$1 \leq Q \leq 3\times 10^5$，$0 \leq n \leq 3\times 10^5$，$0 \leq k \leq 2n$。

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

对于一个多项式 $f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n$，当 $a_i(0 \leq i \leq n)$ 均为非负整数且 $a_n \neq 0$ 时，多项式 $f(x)$ 被称为 $n$ 阶有效多项式。

对于一个 $n$ 阶有效多项式 $f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n$，其孪生多项式 $g(x)$ 定义为

$$g(x) = \sum_{i = 0}^n i \cdot x^{a_i}$$

当且仅当 $f(x) = g(x)$ 时，$f(x)$ 被称为酷多项式。

给出一个不完整的 $n$ 阶有效多项式 $f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n$，$a_i$ 的一部分已经确定，剩余部分暂未确定。保证 $a_0$ 与 $a_n$ 未确定。

请求出确定了未确定的部分以后，能得到多少个 $n$ 阶有效酷多项式。答案对 $10^9 + 7$ 取模。

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

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

设 $v_p(x!)$ 表示 $x!$ 可以分解出多少个 $p$ 的乘积。

勒让德定理：

• 当 $p$ 为质数时

$$v_p(x!) = \sum_{j = 1}^{\lfloor \log_k x \rfloor} \left\lfloor \frac{x}{p^j} \right\rfloor$$

• 当 $p$ 为合数时，记 $p = \sum_{i = 1}^m p_i^{c_i}$

$$v_p(x!) = \min_{i = 1}^m \left\lfloor \frac{v_{p_i}(x!)}{c_i} \right\rfloor$$

设

$$w_k(a, b) = \begin{cases} \min(v_k(a!), v_k(b!)) & \text{if }v_k(a!) \neq v_k(b!) \text{;}\\ 10^{100} & \text{otherwise.} \end{cases}$$

设

$$f_m(a, b) = \min_{2 \leq k \leq m} w_k(a, b)$$

给出两个整数 $n, m$，你需要计算 $\sum\limits_{1 \leq x < n}f_m(x, n)$。

数据范围：$2 \leq n \leq m \leq 10^7$。可以证明给定条件下答案严格小于 $10^{100}$。

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

给出一个长度为 $n$ 的序列 $a_1, a_2, \cdots, a_n$，满足不存在 $1 \leq i < j < k < l \leq n$ 使得 $a_i \neq a_j$，$a_i = a_k$，$a_j = a_l$。

有 $Q$ 次询问，每次询问给出两个整数 $l, r(1 \leq l \leq r \leq n)$，你需要求出区间 $[l, r]$ 中所有出现了奇数次的数之和。

本题强制在线。

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

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

有一个 $n \times m$ 的网格图。最初，每个格点都没有颜色。

每次操作，你可以选择任意一行或一列染色。在第一次操作中，你只能选择颜色 $1$；在第 $i(i > 1)$ 次操作，你可以选择颜色 $c_{i - 1}$ 或 $c_{i - 1} + 1$（其中 $c_{i - 1}$ 表示第 $i - 1$ 次操作选择的颜色）。

如果满足以下条件，我们称最终的染色结果为优美：

• 每个单元格都被染色。
• $1 \sim k$ 的每个颜色都被使用（至少有一个单元格被染成该颜色）。

对于优美的最终染色，我们定义优美值为实现该染色方案最少需要的操作次数。

对于 $i = \min(n, m), \cdots, n + m - 1$，你需要求出优美值为 $i$ 的优美染色个数。

数据范围：$2 \leq n, m \leq 2000$，$1 \leq k \leq n + m - 1$。

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