Link.

今天的题解写得有点水, 没什么参考价值.

∆ A. 出关 (laozi)

可以写出朴素的方程式:

$$f_{i}+A_{s_i} \rightarrowtail f_{i+1} \\ f_i+B+k \times C \rightarrowtail f_{2i-k}$$

$\mathcal O(\frac {n^2}T)$. 其中 $T$ 是某个类似周期的数. 注意字符串是 0-indexed, 而 DP 数组是 1-indexed 的. 对第二个方程换元 $f_i + B + 2i \times C -(2i-k) \times C \rightarrowtail f_{2i-k}$, 令 $v_i = B + 2i \times C + f_i$, 则 $v_i - j \times C \rightarrow f_j$, 那么用线段树维护区间取 min, 单点求值, 标记永久化即可. 求范围需要求解 Z function.

∆ B. 补天 (nvwa)

有点恶心. 首先, 合法的方案一共两种, 取决于第一个放置的颜色. 那么要统计的就是 $(i+j)\bmod 2 = 0$ 的位置数或 $(i+j)\bmod 2 = 1$ 的位置数. 先将所有区间离散化, 使用并查集维护连续段. 并查集的节点上再挂载一个 $cnt_{0/1}$, 分别表示连续段内符合上述两种条件的位置数. 再使用线段树维护区间内... [咕]

∆ C. 理水 (dayu)

发现以前根本没做过正经换根 DP.

先对原图进行边双缩点, 得到一棵树. 如果一个边双连通分量里面存在一条 $1$ 边, 则经过该点的路径均为合法路径. 对于固定的根节点, 设 $f_u$ 表示从 $u$ 出发, $u$ 的子树里的合法节点数. 然后换根即可.

∆ D. 非攻 (mozi)

高一学弟的做法非常简洁, 很有水平! 以下就是他的做法.

考虑固定排列 $P = (p_1, \dots, p_n)$, 连边 $i \rightarrow p_i$, 解决交换次数最小的限制很容易, 注意到每次操作最多让一个环里面的节点变成自环即可. 然后是代价最小的限制, 一个下界是 $\displaystyle \sum m_i(s_i-m_i)$ 其中 $m_i$ 和 $s_i$ 分别表示第 $i$ 个环的最小值和权值和. 手玩发现, 一次交换使一个点变成自环, 剩下的点构成一个新环, 因此这个下界总是取得到.

接下来解决计数. 对一对数 $(i, j)$, 考虑 $i \times j$ 对答案的贡献次数, 这对数对答案产生贡献当且仅当:

• $i$ 是环中最小值;
• $i$ 和 $j$ 在同一环里.

进行构造:

1. 把前 $i-1$ 个数放进图里, 这部分可以随意放, 方案数 $(i-1)!$;
2. 把 $i$ 放进来, 由于 $i$ 是最小值, 因此 $i$ 只能构成一个新环, 方案数 $1$;
3. 把 $j$ 放进和 $i$ 同一环里, 因为此时环里仅有 $i$ 一个元素, 方案数 $1$;
4. 把 $(i, j)$ 和 $(j, n]$ 中的数放进来, 这部分可以随意放, 方案数 $\frac{n!}{(i+1)!}$.

整理以下, 答案就是 $\displaystyle \sum_i \sum_j ij\times \frac{n!(i-1)!}{(i+1)!}$, 预处理阶乘计算即可.

---

/ 如在黑夜中 被熄灭了星空 /

/ 荒原上看不到尽头 /

/ 只有这一路相随的孤独 /

/ 是我黑暗中唯一的盟友 /

—— Kide - 光 ft. 星尘