A

题目要求判断给定的小时数 $x$ 之后，时间是否处于 $6:00$ 到 $18:00$ 之间。

已知起始时间是 $00:00$。经过 $x$ 小时后，当前时刻的小时数为 $h = x \bmod{24}$。

只需要判断 $6 \le h \le 18$ 是否成立即可。

• 如果成立，输出 I love Shawarma。
• 否则，输出 Shawarma is the best food。

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

B

我们需要统计有多少个 $i$ 满足存在区间 $[l, r]$ 使得 $\sum_{j=l}^r a_j = k - a_i$。

记 $target_i = k - a_i$。如果 $target_i \le 0$，显然不存在这样的区间（因为 $a_i$ 均为正整数），可以直接忽略。

对于 $target_i > 0$ 的情况，我们需要快速判断数组中是否存在和为 $target_i$ 的子数组。

注意到数据范围 $n,k \le 5000$，我们可以使用 $O(n^2)$ 的时间预处理出所有可能的区间和。

总时间复杂度 $O(N^2)$，空间复杂度 $O(N)$。

C

由于每一列的掉落是相互独立的，我们可以分别处理每一列。

对于每一列，箱子掉落的规则如下：

1. 箱子会掉落到其下方最近的障碍物（-）或堆叠的箱子/废墟之上。
2. 我们可以从下往上（行号 $n$ 到 $1$）遍历每一列，维护一个变量 $pos$，表示当前物体掉落后的预期放置行号。一开始 $pos = n$。

如果从下往上遍历时（假设此时遍历到第 $i$ 个），会有下面几种情况：

• 遇到了 -，说明下一个物体只能落到这个平台上方，将 $pos$ 设置为 $i - 1$。
• 遇到了箱子，我们可以先计算掉落距离 $pos - i$，然后根据题目要求判断其是否变成*，接着我们把 $pos$ 修改为 $pos - 1$。
• 遇到了 .，直接跳过。

时间复杂度为 $O(nm)$。

D

假设 apiadu 解决 $k$ 个题目，那么 jiangly 就要解决 $n - k$ 个题目。

此时，疲劳值产生的时间是固定的，为：

$$\sum_{x=0}^{k-1} c_x + \sum_{y=0}^{n-k-1} d_y$$

现在的目标是让 $\sum_{i \in S_{\text{apiadu}}} a_i + \sum_{j \in S_{\text{jiangly}}} b_j$ 最小。（其中 $S_{\text{apiadu}}$ 为 apiadu 选择的题目。 $S_{\text{jiangly}}$ 为 jiangly 选择的题目。

将式子变形一下：

$$\begin{aligned} \sum_{i \in S_{\text{apiadu}}} a_i + \sum_{j \in S_{\text{jiangly}}} b_j & = \sum_{i \in S_{api}} a_i + (\sum_{\text{all}} b - \sum_{i \in S_{\text{apiadu}}} b_i) \\ &= \sum_{\text{all}} b + \sum_{i \in S_{\text{apiadu}}} (a_i - b_i) \end{aligned} $$

其中 $\sum_{\text{all}} b$ 是常数。为了使总时间最小，我们需要在确定了 $k$ 的情况下，选择 $k$ 个题目进入集合 $S_{\text{apiadu}}$，使得这 $k$ 个题目的 $(a_i - b_i)$ 的和最小。

故只需要选择 $(a_i - b_i)$ 的 $k$ 个题目给 apiadu 做就能让时间最小。

利用排序和前缀和可以 $O(1)$ 算出 apiadu 解决 $k$ 个题的最小时间。枚举 $k$ 即可。

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

E

先将 $B$ 内的点按照 $a$ 的值从小到大排序，考虑枚举排序后 $B$ 中最编号最大的不在极大匹配中的编号，不妨设为 $k$。

此时我们把点分成 $4$ 类：

1. $A$ 集合中 $[1,a_k]$，称为集合 $1$。
2. $A$ 集合中 $[a_k + 1,n]$，称为集合 $2$。
3. $B$ 集合中 $[1 , k - 1]$，称为集合 $3$。
4. $B$ 集合中 $[k + 1, n]$，称为集合 $4$。

可以发现，集合 $1$ 和集合 $4$ 内的所有点在匹配上。（若集合 $1$ 内存在没有被匹配的点，那么可以让 $k$ 和这个点进行匹配，与题目假设不符；若集合 $4$ 内存在没有被匹配的点，那么 $k$ 就不是编号最大的不在极大匹配中的点。）

那么此时匹配内的边会是在下面几种情况：

1. 集合 $1$ $\leftrightarrow$ 集合 $3$
2. 集合 $1$ $\leftrightarrow$ 集合 $4$
3. 集合 $2$ $\leftrightarrow$ 集合 $4$

对于第一种情况，我们考虑计算其方案数，考虑动态规划。 设 $f_{i,j}$ 表示考虑 $B$ 中排序后的前 $i$ 个点（即 $B_1 \dots B_i$），在 $A$ 中恰好匹配了 $j$ 个点的方案数。 转移方程为：

$$f_{i,j} = f_{i-1, j} + f_{i-1, j-1} \times \max(0, a_i - (j-1)) $$

含义是：$B_i$ 要么不匹配（$f_{i-1,j}$），要么匹配（从 $f_{i-1, j-1}$ 转移）。如果匹配，$B_i$ 可以连接 $1 \dots a_i$ 范围内的任意点，但其中 $j-1$ 个点已经被前面的 $B$ 点占用了，所以有 $a_i - (j-1)$ 种选择。

对于固定的 $k$，我们可以枚举 集合 $1$ 与集合 $3$ 之间的连边数量，设为 $x$。 这部分的方案数即为 $f_{k-1, x}$。

接下来处理剩余的情况：

1. 填补集合 $1$ 的剩余空位（处理情况 $2$）： 集合 $1$（$A[1 \dots a_k]$）的总大小为 $a_k$。既然集合 $3$ 占用了 $x$ 个位置，那么集合 $1$ 中还剩下 $a_k - x$ 个空位。 根据极大匹配的定义（以及 $k$ 是最大未匹配点的假设），这 $a_k - x$ 个空位必须被集合 $4$ 中的点完全覆盖。

2. 集合 $4$ 的分配（处理情况 $3$）： 集合 $4$ 共有 $n-k$ 个点。 其中，必须有 $a_k - x$ 个点用来填补集合 $1$ 的空位。 那么，集合 4 中剩余的点数为：

   $$z = (n - k) - (a_k - x)$$

   这 $z$ 个点必须与 集合 $2$ 中的点进行匹配。

3. 计算总方案数： 由于集合 $4$ 中的点满足 $a_j \ge a_k$，所以它们都可以填到集合 $1$ 的空位上。 因此，计算步骤如下：

4. 从集合 $4$ 中选出 $z$ 个点与集合 2 匹配。考虑用动态规划计算这一步。设 $g[k][z]$ 表示从 $B_{k+1 \dots n}$ 中选 $z$ 个点匹配到 $A_{a_k+1 \dots n}$ 的方案数。

5. 集合 $4$ 中剩下的 $a_k - x$ 个点，用来填充集合 $1$ 的 $a_k - x$ 个特定空位。由于点是不同的，空位也是不同的，这部分的方案数是全排列 $(a_k - x)!$。

故对于固定的 $k$，其对答案的贡献为：

$$\sum_{x} \left( f_{k-1, x} \times g[k] [(n-k) - (a_k - x)] \times (a_k - x)! \right) $$

如何计算 $g$ ？考虑通过 $g[k]$ 转移到 $g[k - 1]$。

可以发现，当 $k$ 减少 $1$ 时，集合 $2$ 会新增 $L = a_k - a_{k - 1}$ 个点，且这些点都可以被集合 $4$ 内的点连接。

我们可以把这 $L$ 个空位一个一个加入，假设我们要加入一个新的点，设 $g_0[z]$ 为更新前的状态，$g_1[z]$ 为更新后的状态，那么会有以下两种情况：

1. 这个点没有被使用，此时贡献为 $g_0[z]$。
2. 这个点被使用，此时贡献为 $g_1[z - 1] \times (M - z+ 1)$，其中 $M$ 表示集合 $4$ 的大小。

由于新增了 $L$ 个位置，我们只需要将上述过程重复 $L$ 次即可。

最后加上所有 $B$ 点都匹配（完美匹配）的情况，即 $f_{n,n}$。

时间复杂度为 $O(n^2)$。

F

不妨设以 $1$ 为根，对于某个节点 $u$，先考虑如何计算以 $u$ 为起点的子树内所有路径权值之和。

定义$S(u, v)$ 为 $u \to v$ 的路径上所有 sqr k 操作参数 $k$ 的和。 根据题目定义，$d(u, v)$ 的计算过程为：初始值 $1$，依次经过路径操作。 若路径上某条边为 * C，且该边之后（在通往 $v$ 的方向上）累积经过了 $S'$ 次平方操作，则因子 $C$ 在最终结果中会变为 $C^{2^{S'}}$。

由于指数 $S$ 可能很大，根据费马小定理和扩展欧拉定理，我们有如下性质：

• 在模 $P=998244353$ 下，底数的指数是模 $P-1$ 的。
• $2^S \pmod{P-1}$ 具有长度为 $23$ 的前缀和长度为 $24$ 的循环。
• 故总共只有 $23 + 24 = 47$ 种本质不同的指数状态。我们将 $S$ 映射到 $[0, 46]$ 的范围内，记为 $\text{Map}(S)$。

所以我们按照这个指数状态对路径进行分类。

故设 $f[u][i]$ 表示 $u$ 的子树中，所有满足 $\text{Map}(S(u, v)) = i$ 的节点 $v$ 的路径值之和，即：

$$f[u][i] = \left( \sum_{v \in \text{subtree}(u), \ \text{Map}(S(u,v))=i} d(u,v) \right) \bmod P $$

此时考虑转移，当合并子节点 $v$ 到 $u$，且边 $u \to v$ 的值为 $k$ 时：

• 假设边为 sqr k： 从 $u$ 出发的第一步是对初始值 $1$ 进行平方，$1^{2^k}=1$，故数值不变。 但是对于子树中的任意节点 $w$，有 $S(u, w) = S(v, w) + k$。 这意味着原本属于状态 $i$ 的路径，现在的状态变为 $i+k$。 故转移方程为：

  $$f[u][i+k] \leftarrow f[u][i+k] + f[v][i]$$

• 假设边为 * k： 从 $u$ 出发的第一步是将初始值 $1$ 乘以 $k$，变为 $k$。 此后从 $v$ 继续走到子树节点 $w$，这个因子 $k$ 将会被后续的 sqr 操作平方 $S(v, w)$ 次。 即新的路径值为 $d(u, w) = k^{2^{S(v, w)}} \times d(v, w)$。 此时路径的 $S$ 值没有变化，$S(u, w) = S(v, w)$。 故对于状态 $i$（即 $S(v, w)=i$），所有路径的值都要乘以 $k^{2^i}$。 转移方程为：

  $$f[u][i] \leftarrow f[u][i] + f[v][i] \times k^{2^i} $$

此时 $\sum_{j=1}^{n} d(1, j)$ 的答案为 $\sum_{i=0}^{46} f[1][i]$。

其他位置的答案，可以通过换根 dp 来解决，这里不再赘述。

时间复杂度为 $O( 47\times n)$。