CSP2024-14

A

题意：给定一张边权为正的无向图，\(k\) 条关建边，求从 \(1\) 经过所有关建边回到 \(1\) 的最短路。\(k \le 12\)。

所有关键边的端点加上 \(1\) 也就 \(25\) 个，\(f(x, S)\) 表示当前在 \(x\)，已经经过的关键边集合为 \(S\) 的最短路，随便转移。

傻逼人干傻逼事，最短路不开 long long 调半天。建议 hydro 学学 cf 给个越界提示。submission

B

题意：给定字符串 \(s, t\)，两个串相似定义为 \(s\) 可以翻转恰好一个非空区间得到 \(t\)。

\(q\) 次修改，每次修改 \(s\) 的一个字符，求使两串相似的方案数以及最小翻转区间长度。\(\vert s\vert,\ \vert t\vert,\ q \le 10^6\)。

如果 \(s = t\)，翻转区间一定满足回文，可以对 \(t\) 二分 + 哈希预处理（实际是不会 manacher）。

令 $S = {i \mid s_i \ne t_i},\ l = \min_{x \in S} x,\ r = \max_{x \in S} x $。

对于一个翻转区间 \([L, R]\)，显然有 \([l, r] \subseteq [L, R]\)，现在说明 \(l - L = R - r\) 是方案合法的必要条件。

如果 \(l - L < R - r\)，\(l\) 在操作后会到达位置 \(x = R - (l - L) > r\)，也就是 \(s_x = t_x\)，同时有 \(s_x = t_l \land s_l = t_x\)，与 \(s_l \ne t_l\) 矛盾。

如果翻转 \([l, r]\) 不合法则无解，否则二分左右边界。

单点修写线段树会多一个 log，考虑只维护 \(s\) 整串的哈希，然后比对 \(t[1, l)[r, l](r, n]\)，时间复杂度 \(O\big((\vert s\vert + t) \log \vert s\vert\big)\)。submission

C

D

题意：\(n\) 个点的树，每次可以删一条边再加一条，使得他还是一棵树。求 \(k\) 次操作后树有多少不同形态（有标号无根）。

数据范围：\(k \le n \le 5000\)。

前置知识：图连通方案数。

背景：\(n\) 个点 \(k\) 个连通块的无向图，求加 \(k - 1\) 条边使之连通的方案数。

先把连通块看作点，设第 \(i\) 个连通块在缩点后的树上有度数 \(d_i\)，度数和等于边数的两倍，即 \(\sum_{i = 1}^k d_i = 2k - 2\)。

一个点在 prufer 序列中出现的次数等于其度数减 \(1\)。那么当度数确定时，方案数等于 \(\dfrac{(k - 2)!}{(d_1 - 1)!(d_2 - 1)!\cdots (d_k - 1)!}\)。

考虑把点还原成连通块，一个度数为 \(d\) 的连通块有 \(s^d\) 种连边方式，\(s\) 是其大小。

枚举度数，令 \(e_i = d_i - 1\)：

\[\begin{aligned} &=\sum_{d_i \ge 1, d_1 + d_2 + \cdots + d_k = 2k - 2}\begin{pmatrix}k - 2\\d_1 - 1, d_2 - 1, \cdots, d_k - 1\end{pmatrix}\prod_{i = 1}^ks_i^{d_i}\\ \\ &=\sum_{e_i \ge 0, e_1 + e_2 + \cdots + e_k = k - 2}\begin{pmatrix}k - 2\\e_1, e_2 - 1, \cdots, e_k\end{pmatrix}\prod_{i = 1}^ks_i^{e_i + 1}\\ \\ &= (e_1 + e_2 + \cdots + e_k)^{k - 2}\prod_{i = 1}^k s_i \\ \\ &= n^{k - 2} \prod_{i = 1}^k s_i \end{aligned} \]

实际上就是求与原树最多有 \(k\) 条边不同的方案数，即相同边连成的连通块至多 \(k + 1\) 个。

考虑