T1

100%

如果 $T$ 正好是某一班车的发车时刻，那么答案就是 $0$。否则，设 $T$ 距离最近的上一班车还差 $r=(T-S)\bmod K$，那么还需要等待的时间就是 $K-r$。把这两种情况合并起来，答案可以写成：

$$(K-(T-S)\bmod K)\bmod K$$

直接按这个式子计算即可，当然也可以用 if 语句进行分类讨论。

时间复杂度 $O(1)$。

T2

100%

由于题目保证只有 [说明] 的两侧有括号，因此从左到右扫描字符串，找到第一个 [ 和第一个 ] 的位置，输出中间的子串即可。

时间复杂度 $O(|s|)$。

T3

100%

设原串中 0 的个数为 $c_0$，1 的个数为 $c_1$。最终要求两者数量相同，所以最少需要修改的字符数 $k$ 为：

$$k = \frac{|c_0-c_1|}{2}$$

接下来考虑字典序最小。

• 如果 0 的数量更多，那么需要把一部分 0 改成 1。为了让字典序尽量小，应该尽量保留前面的 0，所以选择修改最靠右的 $k$ 个 0。
• 如果 1 的数量更多，那么需要把一部分 1 改成 0。为了让字典序尽量小，应该尽量让前面变成 0，所以选择修改最靠左的 $k$ 个 1。

因此只需统计两种字符的数量，再按上述规则从左或从右挑出需要修改的位置即可（但输出下标时，需要从左往右输出）。

时间复杂度 $O(n)$。

T4

100%

这是一个树上自底向上的贪心。

题目要求对任意祖先 $u$ 和后代 $v$，满足最终高度 $h_u>h_v$。由于我们只能让高度增加，所以一个节点最终至少要比它所有儿子的最终高度都大 1。也就是说，如果一个节点 $u$ 的儿子中的最终高度最高的是 $H$，那么这个节点 $u$ 最终至少要变成 $H+1$；如果它原本更大，则不需要额外修改，即：

$$h_u=\max\Bigl(h_u,\max_{v\in son(u)} h_v+1\Bigr)$$

因此，从根节点开始做后序 DFS：

• 先递归处理所有子节点；
• 取所有子节点最终高度的最大值 $H$；
• 当前节点最终高度应当更新为 $\max(h_u, H+1)$；
• 需要执行的操作次数就是这个新值减去原值，累加到答案里。

这样处理后，当前节点会自动满足“比所有后代都高”，并且对子树以外的部分没有额外影响，因此这是最优的。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

T5

100%

为了击败邪教徒，我们至少需要总共打出 $nd = \left\lceil \frac{HP}{S} \right\rceil$ 张打击牌。

接下来考虑如何在保证总打击牌数至少为 $nd$ 的前提下，让机宝剩余血量尽可能多。

对于每一回合，我们贪心地尽可能打出多的打击牌。

具体来说，第 $i$ 回合打出 $U=\min(u_i, k_i)$ 张打击牌，剩余的牌全部用于防御，即 $V=\min(v_i, k_i-U)$。此时该回合机宝受到的伤害是 $\max(w_i-V \times D, 0)$。

如果按照这个贪心策略打到某一回合，机宝的总打击牌数超过了 $nd$，且承受的总伤害没有让机宝死亡，那么超出的打击牌其实就是“冗余”的。我们可以把这些冗余的打击牌“撤回”，替换成防御牌，从而进一步减少受到的伤害，提高最终剩余血量。

当我们将一张打击牌改为防御牌时（即反悔操作），该回合防御值增加 $D$。观察伤害 $\max(w_i-V \times D, 0)$ 随 $V$ 的增加，减小量（即反悔收益）有两阶段特征：

如果当前 $V \times D < w_i$ （即该回合收到伤害了）：

1. 在伤害降为 0 之前，每多 1 张防御牌，伤害稳定减少 $D$。
2. 当伤害即将从 $R=w_i \mod D$ 降至 0 时，这 1 张防御牌，只能减少 $R$ 点伤害。

由于每个回合可选的反悔操作的收益是单调不增的（先是若干个 $D$，再是至多一个 $R$，最后都是 0），因此我们可以使用 大根堆（优先队列） 来维护所有可用的反悔操作。

具体流程：

1. 初始化：计算必须打出的打击牌数量 $nd = \left\lceil \frac{HP}{S} \right\rceil$。维护当前打出的打击牌总数 $cnt$，和当前累计受到伤害 $damage$。
2. 模拟每一回合的操作：
   • 贪心打出 $U=\min(u_i,k_i)$ 张打击牌，$V=\min(k_i-U,v_i)$ 张防御牌。
   • 令 $cnt+=U$，$damage+=\max(w_i-V \times D,0)$。
   • 如果当前回合防御牌未打满（$V<v_i$），且仍在掉血（$V \times D < w_i$），计算可反悔的次数和收益，压入大根堆（按收益从大到小排序）：
     • 可反悔操作首先受打击牌和防御牌数量的限制，即 $can=\min(U,v_i-V)$。
     • 实际受到伤害为 $get = w_i-V \times D$，因此收益为 $D$ 的次数 $num$ 为 $\left\lfloor \frac{get}{D} \right\rfloor$，压入大根堆。
     • 若 $can > num$ 且 $w_i \mod D \neq 0$，说明还可以有一次收益为 $w_i \mod D$ 的操作，压入大根堆。
   • 反悔过程：只要当前总打击牌数量 $cnt > nd$ 且堆不为空，说明我们有冗余的打击牌可以用来反悔。弹出堆顶操作（收益 $val$，次数 $num$），将尽可能多的打击牌换成防御牌，并更新 $cnt$ 和 $damage$。
   • 若在某一回合的调整结束后，$damage < hp$（机宝存活）且 $cnt \geq nd$，说明当前是一种可行的获胜状态，更新最大剩余血量。
3. 输出最大剩余血量或 -1。

时间复杂度约为 $O(n\log n)$。

T6

100%

我们需要计算：

$$S = \sum_{a' \in \mathrm{perm}(a)} \sum_{b' \in \mathrm{perm}(b)} F(a', b')$$

其中

$$F(x, y) = \sum_{1 \le i_1 < \dots < i_m \le n} \prod_{j=1}^{m} x_{i_j}^{y_j}.$$

将 $F$ 代入并交换求和顺序：

$$S = \sum_{a'} \sum_{b'} \sum_{1 \le i_1 < \dots < i_m \le n} \prod_{j=1}^{m} (a'_{i_j})^{b'_j}.$$

重新组织求和：对于固定的 $a$ 的大小为 $m$ 的子序列（保持原下标顺序），以及固定的 $b$ 的一种排列，计算这些值在所有 $a'$ 中出现多少次。

• 从 $a$ 中选出 $m$ 个元素，并按选出的顺序放入子序列位置，有 $P(n, m) = \frac{n!}{(n-m)!}$ 种方式。
• $a$ 中剩余的 $n-m$ 个元素可以任意排列在剩下的位置上，有 $(n-m)!$ 种方式。
• 两者相乘，表示每种“有序的 $m$ 元子序列 + 剩余元素排列”恰好对应一个完整的 $a'$，出现次数为 $P(n,m) \times (n-m)! = n!$。

因此，$b'$ 取遍所有 $m!$ 种排列，而 $a'$ 的求和可以转化为对 $a$ 的所有大小为 $m$ 的有序子序列求和，再乘上 $n!$：

$$S = n! \sum_{1 \le i_1 < \dots < i_m \le n} \sum_{b' \in \mathrm{perm}(b)} \prod_{j=1}^{m} a_{i_j}^{b'_j}.$$

这样我们就把问题分解为两部分：

• 计算 $T = \sum_{1 \le i_1 < \dots < i_m \le n} \sum_{b' \in \mathrm{perm}(b)} \prod_{j=1}^{m} a_{i_j}^{b'_j}$；
• 最终答案 $S = n! \cdot T$。

其中 $T$ 的含义是：在序列 $a$ 中按原顺序挑选 $m$ 个元素构成子序列，同时将 $b$ 的所有排列作为指数分配给这些元素，求所有乘积之和。

这可以通过动态规划解决。我们按顺序遍历 $a$ 的每个元素，并逐步决定它是否被选入子序列，以及如果被选中，它对应 $b$ 中的哪一个指数。为了不重不漏地枚举 $b$ 的所有排列，我们还需要记录 $b$ 中哪些位置已经被分配，由于 $m \leq 10$，因此可以通过二进制状态来表示。

状态定义： 用二进制掩码 $\mathrm{mask}$ 表示当前已经使用了 $b$ 中的哪些元素（$0 \le \mathrm{mask} < 2^m$）。
$\mathrm{dp}[\mathrm{mask}]$ 表示在当前已经考虑过的 $a$ 的前缀中，选出的子序列已经占用了 $\mathrm{mask}$ 中的 $b$ 元素时，所有合法方案的乘积之和。

转移： 顺序遍历 $a$ 中的每个元素 $a_i$（代码中保持原始顺序）。对于当前的 $a_i$，我们有两种选择：

1. 不选 $a_i$：$\mathrm{dp}[\mathrm{mask}]$ 保持不变。
2. 选 $a_i$，并把它分配给 $b$ 中某个尚未使用的指数 $b_j$（$j \notin \mathrm{mask}$）： 此时新状态为 $\mathrm{mask} \cup \{j\}$，贡献要乘上 $a_i^{b_j}$。

写成递推式，对于当前 $a_i$：

$$\mathrm{new\_dp}[\mathrm{mask}] = \mathrm{dp}[\mathrm{mask}] + \sum_{j \in \mathrm{mask}} \mathrm{dp}[\mathrm{mask} \setminus \{j\}] \cdot a_i^{b_j}$$

其中 $j \in \mathrm{mask}$ 等价于“在上一步状态 $\mathrm{mask} \setminus \{j\}$ 的基础上，选用 $a_i$ 并匹配 $b_j$”。

初始化： 未考虑任何 $a$ 元素时，空集状态乘积为 $1$：$\mathrm{dp}[0] = 1$，其余为 $0$。

最终结果： 处理完 $a$ 的全部 $n$ 个元素后，$\mathrm{dp}[(1 \ll m) - 1]$ 即为所需的 $T$——它恰好枚举了所有大小为 $m$ 的 $a$ 子序列，以及 $b$ 的所有排列与之匹配的情况。

由前面的推导，答案即为：

$$S = n! \cdot \mathrm{dp}[(1 \ll m) - 1] \bmod 998244353.$$

时间复杂度为 $O(nm2^m)$（幂运算可以提前 $O(nm \log V)$ 预处理并保存到数组中），空间复杂度为 $O(2^m)$（滚动数组优化空间，否则为 $O(n2^m)$）。