A. 铁甲战士

除了最开始，抽牌堆里至少包含一张牌，也就是刚打出的那张。下面默认抽牌堆里已经包含一张牌。可以发现，如果在出剑柄打击后不出耸肩无视，那么后面迟早会把手牌全部出完，无法持久地打下去，所以剑柄打击后必须出耸肩无视。同理，如果出了一张狂怒/全身撞击，那么下一张必须要打剑柄打击。因此除了游戏开头，一定是狂怒/全身撞击，剑柄打击，耸肩无视循环出。对于游戏开头和结尾只有 $O(1)$ 种可能，可以直接枚举。可以发现，一定是一个前缀打狂怒，一个后缀打剑柄打击，直接二分分界点即可。需要写高精度。

B. 小青鱼

如果每次操作是操作一整行/列/对角线，那么题目等价于 3sum 问题，可以用一次 FFT 解决。

那么现在区间怎么做。考虑分块。把 $n\times n$ 分成 $n/B\times n/B$ 个 $B\times B$ 的块。这样每一条线会经过 $O(n/B)$ 个整块和 $O(B)$ 个散点。整块同样 FFT。散点暴力加入。复杂度 $O(n\sqrt{n\log n})$。

不想要这个 $\log n$ 因子。可以发现行的多项式的点值可以在横着扫时保留。每次更新一个单点系数可以 $O(B)$ 改完点值。对列和斜同理。这样 $\log n$ 就没了。复杂度 $O(n\sqrt n)$。

C. 货币

相当于对每个 $i$，我们需要在 $(1,i)$ 到 $(1,i+1)$ 与 $(2,i)$ 到 $(2,i+1)$ 之间选择一个走。选每一种需要一个代价，如果 $i$ 和 $i+1$ 选择了不同的行，那么就需要额外付出 $(1,i+1)$ 到 $(2,i+1)$ 之间边的代价。再加上 $m$ 条限制，是一个小型的切糕模型，直接建图跑网络流即可。

D. 广为人知题 2

本题为 IDM Problem 的 CountDistinct 查询。详细做法见 Nearly Optimal Internal Dictionary Matching。

给所有串赋一个权值 $v_t$，其中 $t$ 为一个 $s$ 的子串，初始均为 $0$。我们直接将所有模式串对应的 $v_t$ 加 $1$，查询的答案即为查询串 $s[l,r]$ 所有本质不同子串中 $v$ 的和。

考虑所有串形成的 trie（这里 trie 字符着加，为了匹配正串 SAM）。记 $f_u$ 为 $u$ 到根的所有串的 $v$ 之和。答案为 trie 上所有是 $s[l,r]$ 子串的点的 $v$ 之和。显然构成一个 trie 上包含根的连通块，答案即为：

$$\sum\limits_{u是叶子}f_u-\sum\limits_u (u儿子个数-1)f_u$$

首先考虑后者。按 $r$ 扫描线，考虑 LCT，维护 SAM 上连续上一次出现位置相同的节点。每次 access 时遇到一个连续段时，考虑段尾的点何时儿子个数 +1，应为 $l\leq \mathrm{last}-\mathrm{len}$ 且 $s[1,r]$ 所在子树第一次出现节点（即上一个连续段中的 $\mathrm{last}$ 不会在这里贡献）。所以对 $l$ 是一个区间加。查询即为单点查询。该部分时间复杂度 $O(n\log^2n+q\log n)$。

再考虑前者。首先叶子一定左端点为 $l$。其次若 $s[l,t]$ 非叶子，说明存在 $s[l',r']=s[l,t]$ 且 $t

最后考虑如何求出 $\sum\limits_{i=x}^r f_{s[l,i]}$。差分后变为若干个 $\sum\limits_{i=l}^r f_{s[l,i]}$。而这等价于广为人知题查询（IDM Problem 的 Count 查询），可以用基本子串结构（见 Nearly Optimal Internal Dictionary Matching）在 $O((n+q)\log n)$ 内解决。

总时间复杂度为 $O(n\log^2 n+q\log n)$。若 $n,q$ 同阶，可优化至 $O\left(\frac{n\log^2n}{\log\log n}\right)$。

E. 浅斟低唱

考虑维护长度 $\geq 2$ 的所有 0 的连续段和 1 的连续段，每次 1 操作是让所有 0 连续段左移一位，所有 1 连续段右移一位，2 操作同理。

例子：经过 1 操作后，

01010000111101010001110111100010101 变成

10100001011110100010111011100101010

唯一出现问题的可能即为存在一个 0 连续段与一个 1 连续段撞上了。此时可以暴力修改，由于所有连续段长度总和这时会减 2，且长度总和初始最多为 $n$，修改最多增加在每次操作的边界 ，所以总暴力修改次数为线性。

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

F. Trash Problem

枚举左边界。此时从左往右扫，记录每个格子当前是一个 $2\times 2$ 的一半还是已经完成。每次扫的时候如果当前是一半但是下一个是黑格，那么包含这一行的就全不合法。否则如果当前是白格，就将这个状态异或 $1$。扫到某个时刻，一个区间合法当且仅当当前这些状态都是已完成，且这个区间不包含前面所说的那些行，且与所有出现过的连续状态 $1$ 的区间交的长度为偶数。前两个条件容易满足，重点在于第三个条件。

可以发现，$[l,r]$ 与所有连续状态 $1$ 的区间交的长度为偶数等价于 $[1,r]$ 与所有连续状态 $1$ 的区间交的长度为奇数的区间左端点集合等于 $[1,l-1]$ 与所有连续状态为 $1$ 的区间交的长度为奇数的区间左端点集合相同。直接扫描线扫 $r$，哈希一下，如果哈希表 $O(1)$ 复杂度即为 $O(n^3)$。

G. 分析

注意到代价为 $A$ 的操作可以直接视为加了一条重边，所以我们可以先执行所有代价为 $A$ 的操作，在考虑怎么走。可以发现加完边之后需要执行的 $B$ 操作次数即为度数为奇数的点数除以 $2$ 再 $-1$（如果没有度数为奇数的点即为 $0$）。

树形 dp，过程中考虑是否加重边，状态内记子树根的度数奇偶性和是否有度数为奇数的点即可。

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

H. 代数

题解

首先把子树大小的 $k$ 次方改为选 $k$ 个点都在子树内的方案数。进一步，可以看作有 $n+1,n+2,\dots,n+k$ 这 $k$ 个点，每个点随机选择 $1,2,\dots,n$ 中的一个点作为父亲，问有多少种方案使得它们都在 $u$ 子树内。

考虑从前往后 dp，设 $d[i][j]$ 表示前面 $i$ 个点考虑完，有 $j$ 个点还存在没出现的儿子的子树里有 $n+1,\dots,n+k$ 这 $k$ 个点之一。那么转移即为：

1. 新出现的点子树里没有 $n+1,\dots,n+k$ 这 $k$ 个点之一。那么随便接到任意一个点上即可。
2. 新出现的点子树里有这 $k$ 个点之一，假设接到了点 $u$ 下面，此时 $u$ 还有别的没出现的儿子的子树里有这 $k$ 个点之一。
3. 新出现的点子树里有这 $k$ 个点之一，假设接到了点 $u$ 下面，使得 $u$ 没有没出现的儿子的子树里有这 $k$ 个点之一。

要计算每个点的答案，需要从前往后做一遍，转置之后从后往前再做一遍，最后在中间统计答案即可。

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

I. 二十二

首先忽略所有没有用的操作。其次，全局取 min 操作一定是从小到大操作的，因为如果有两个前面大右边小，前面的一定没用，可以把它放到紧挨着小的的右边，也没用。这样每一个 max 操作就可以放在任何一个 min 操作前面，可以看作对（这个 min 对应的 $c$ 或者原本的 $c$）取 max。

所以结论即为把所有区间 max 操作的 $c$ 变为所有比 $c$ 小的 min 操作的值之一或者不变后，先操作最小的全局 min，后操作所有 max 操作，有多少种最终序列。可以区间 dp，dp 数组类似 $dp(l,r,x)$，表示区间 $[l,r]$ 内最终序列的所有数均 $\geq x$ 且 $l-1,r+1$ 两个位置 $< x$ 的方案数。因为这样只需考虑被 $[l,r]$ 包含的 max 操作。每次枚举区间最小值转移即可，会有亿点细节。

在 $n,m,k$ 同阶时，时间复杂度为 $O(n^4)$。

J. 我以渺小爱你

条件等价于把每条 hyperedge $(x,y,z)$ 拆成三条边 $(x,y),(y,z),(z,x)$ 后建成的无向图中不包含四元环。

首先构造图 $\mathrm{ER}_q$：

点：$\bmod q$ 意义下三维空间的所有不同直线。

边：两条直线垂直。

容易证明 $\mathrm{ER}_q$ 有点数 $q^2+q+1$，边数 $\frac 12 q(q+1)^2$，且图中不存在四元环。

构造答案：hyperedge 为 $\mathrm{ER}_q$ 中所有的三角形。容易验证满足边数条件。

K. 应氏杯

在钦定一个点是极小值之后，它和周围点之间的大小关系就确定了。

一个经典结论：对于一个森林，如果所有父亲小于儿子，那么赋一个排列的方案数为 $n! \prod_u \frac 1{siz_u}$。

考虑树形 dp，记 $d[u][i][j]$ 为 $u$ 子树内，钦定了 $i$ 个点为极小值，当前小于关系构成的子树大小为 $j$ 的方案数。每次钦定一个点为极小值时，它小于所有儿子，且小于它的父亲。小于它的父亲可以通过容斥变为无限制减去父亲小于它。

是一个二维背包。把一维改成维护点值+插值之后，可以做到 $O(n^3)$。