ARC171 题解

A - No Attacking

先考虑车的放置，任意两个车不能在同一行或同一列，考虑尽可能为兵预留出位置，也就是尽量间隔放置。

B - Chmax

容易想到建图，对部分点建出唯一后继，若 $i\lt P_i$ 则 $i$ 的终点为 $P_i$，那么从 $1$ 到 $N$ 扫描，若 $i\gt P_i$ 则无解，$i\le P_i$ 若 $i$ 为某个点终点则无解，否则有唯一建图方式，$i=P_i$ 则可以任意选择空指向已经开始的起点。

C - Swap on Tree

考虑树上 DP，对于点 $u$ 如何合并儿子的答案。显然每个点对于是否和父亲交换有两种可能 $f_{u,0/1}$，那么先将所有儿子 $v$ 做一遍背包，使得 $g_{x}$ 为有 $x$ 个儿子与 $u$ 交换。考虑 $g_{x}$ 对 $f_{u,0/1}$ 的贡献，相当于抽出了一个以 $u$ 为根的菊花图，每一次可以任意选择一条边进行交换，贡献系数是阶乘。

D - Rolling Hash

考虑前缀哈希值 $P_i$，每一个限制等价于 $P_r \not\equiv P_{l-1}B^{r-l+1}(\bmod p)$，既然 $p$ 是质数，将 $P_i:=\frac{P_{i}}{B^i}$，则等价于 $P_r \not\equiv P_{l-1}(\bmod p)$。相当于点染色使得不存在邻点同色。可以对导出子图状压 DP，转移时枚举独立集。但是搜索 + 随机化 + 卡时可以通过。