T1

100%

满分当且仅当实际得分等于满分，即判断 $a=b$。

• 若 $a=b$，输出 Accepted；
• 否则输出 Unaccepted。

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

T2

100%

按照题意依次处理每一件装备，并始终保存当前战斗力对 $998244353$ 取模后的值 $ans$。

• 遇到 A x，令 $ans=(ans+x)\bmod 998244353$

• 遇到 B x，令 $ans=(ans\times x)\bmod 998244353$

每次操作后输出 $ans$ 即可。乘法计算的中间结果需要使用 long long。

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

T3

100%

怪物是否能被击败取决于它出现时的战斗力，因此必须按照时间顺序处理怪物，而不是按照输入顺序处理。

将每个怪物保存为三元组 $(t_i,x_i,y_i)$，按照 $t_i$ 从小到大排序。随后依次处理：

• 如果当前战斗力 $s\ge x_i$，则击败该怪物，令 $s:=s+y_i$；
• 否则战斗力不变。

所有 $t_i$ 互不相同，因此排序后不会出现同一时刻的处理顺序问题。

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

T4

40%

当 $n\le 15$ 时，可以枚举每天进行的三种操作，并检查游戏天数、游戏是否连续以及做题专题是否交替，取所有合法方案的最大收益。

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

100%

“相邻两道题目的专题不同”中的两道题不一定在相邻两天，因此只记录前一天做了什么是不够的。我们需要同时记录：

• 最近一次刷题的专题；
• 前一天是否在玩游戏。

设 $dp_{i,j,t,g}$ 表示已经安排完前 $i$ 天、恰好玩了 $j$ 天游戏时的最大收益，其中：

• $t\in\{0,1,2\}$：最近一次刷题的专题，$0$ 表示套路题，$1$ 表示思维题，$2$ 表示还没有刷过题；
• $g\in\{0,1\}$：前一天是否在玩游戏。

初始时只有：

$$dp_{0,0,2,0}=0$$

其余状态均为负无穷。

考虑第 $i+1$ 天，设其收益为 $a_{i+1},b_{i+1}$，从每个合法状态进行下面的转移。

1.玩游戏：只有前一天没有玩游戏，即 $g=0$ 时才可以选择：

$$dp_{i+1,j+1,t,1}=\max(dp_{i+1,j+1,t,1},dp_{i,j,t,0}) $$

最近一次刷题的专题 $t$ 保持不变。

2. 刷套路题：只有 $t\ne 0$ 时才可以选择：

$$dp_{i+1,j,0,0}=\max(dp_{i+1,j,0,0},dp_{i,j,t,g}+a_{i+1}) $$

3. 刷思维题：只有 $t\ne 1$ 时才可以选择：

$$dp_{i+1,j,1,0}=\max(dp_{i+1,j,1,0},dp_{i,j,t,g}+b_{i+1}) $$

处理完 $n$ 天后，在所有 $dp_{n,m,t,g}$ 中取最大值即可。

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

T5

100%

先固定所有人的总安检顺序。由于 $n$ 个人互不相同，总顺序共有 $n!$ 种。

对于一个固定的总顺序，设某一批有 $k$ 个人。该批需要从 $m$ 个不同安检口中选择 $k$ 个，并且不记录人与安检口之间的具体对应关系，因此这一批的方案数为 $\binom{m}{k}$。

接下来只需要统计：将固定顺序的前 $n$ 个人划分成若干个连续非空批次，每一批大小不超过 $m$，且大小为 $k$ 的批次带有 $\binom{m}{k}$ 种选择时，共有多少种方案。

设 $f_i$ 表示固定总顺序后，安排完前 $i$ 个人的方案数。初始值为：$f_0=1$。

枚举最后一批的人数 $k$。最后一批之前的 $i-k$ 个人有 $f_{i-k}$ 种安排，最后一批有 $\binom{m}{k}$ 种安检口集合，因此：

$$f_i=\sum_{k=1}^{\min(i,m)}f_{i-k}\binom{m}{k}$$

最终答案为 $n!\,f_n$。

时间复杂度 $O(n\min(n,m))$，空间复杂度 $O(n)$。

T6

100%

对于一次 2 l r k 操作，如果选择第 $i$ 个专题，那么从它的 $a_i$ 道题中选择 $k$ 道的方案数为 $\binom{a_i}{k}$。由于一次集训只能选择一个专题，所以查询的答案是：

$$\sum_{i=l}^{r}\binom{a_i}{k}$$

问题转化为：维护序列 $a$ 的区间加，并查询区间内组合数之和，其中 $k\le 8$。

记 $K=8$。对于线段树的每个结点和每个 $0\le j\le K$，维护：

$$S_j=\sum_{i\text{ 在该结点区间内}}\binom{a_i}{j}$$

其中 $\binom{x}{0}=1$，所以 $S_0$ 就是该结点对应的区间长度。

合并两个儿子时，将对应的 $S_j$ 分别相加即可。查询 2 l r k 时，查询区间的 $S_k$ 即为答案。

如果一次修改使 $a_i$ 变为 $a_i+y$，由根据范德蒙德卷积有：

$$\binom{a_i+y}{j} =\sum_{t=0}^{j}\binom{a_i}{t}\binom{y}{j-t} $$

对结点区间内的所有 $i$ 求和，得到修改后的维护值：

$$S'_j =\sum_{t=0}^{j}S_t\binom{y}{j-t}$$

因此，对一个完整覆盖的线段树结点，可以先求出：

$$c_d=\binom{y}{d}\quad(0\le d\le K)$$

然后在 $O(K^2)$ 时间内更新整个 $S$。计算新的 $S$ 时必须使用修改前的各个 $S_t$，可以复制一份旧数组后再转移。

下传标记时，分别对两个儿子的 $S$ 值执行同样的操作即可。

每次修改和查询的时间复杂度均为 $O(K^2\log n)$，空间复杂度为 $O(nK)$。