2025 CCPC 济南 / UCUP 4. Stage 9: GP of Jinan

补题很吃力。

ID	Diff	Description	Solution	Code	Review
A	Master	求满足 $A^{n} \equiv B \pmod{2^{64}}$ 的最小非负整数 $n$，或报告无解。	当 $A$ 是偶数时，若 $n \geqslant 64$，$A^{n}=(2A_{1})^{n} \equiv 0$，于是只需枚举 $n = 0, 1, \dots, 64$。当 $A$ 是奇数时，如果考察 $(2 A_{1} + 1)^{n}$ 或 $(\sum 2^{i} A_{i})^{n}$，会产生大量二项式系数，没有很好的性质。考虑从 $n$ 入手，将 $n$ 二进制分解，考察每个 $A^{2^{k}}$ 对答案的影响，其中 $k \geqslant 1$。先看 $A^{2^{k}} \equiv 1 \pmod {2^{r}}$，这是说乘上 $A^{2^{k}}$ 对答案的低 $r$ 位没有影响。条件等价于 $\nu_{2}(A^{2^{k}} - 1) \geqslant r$，记 $f_{k} = \nu_{2}(A^{2^{k}} - 1) = \nu_2(A-1)+\nu_2(A+1)+k-1$。$f_{k}$ 递增，因此 $n$ 中比 $k$ 高的二进制位，无法再改变 $A^{n}$ 中的低 $f_{k}$ 位。在确定 $n$ 的第 $k$ 位时，就需要保证 $A^{n}$ 的低 $f_{k+1}$ 位与 $B$ 相同。从低到高位枚举，对于第 $k$ 位，如果当前 $A^{n} \not\equiv B\pmod{2^{f_{k+1}}}$，更新 $n\leftarrow n+2^k$。	AC
C	Medium	序列 $A$ 和排列 $B$，求 $A$ 最多能选出多少个互不重叠的子序列，使得每个子序列均等于 $B$。	$f(i,j)$：考虑序列 $A[0, i)$ 前 $i$ 个字符，已经匹配 $B[0, j)$、等待继续往后匹配的子序列数量，转移只需要 f[pos[x] - 1]--; f[pos[x]]++;。$\mathcal{O}(\vert A \vert + \vert B \vert)$。	AC
E	Expert	带颜色的树。求集合对 $(S, T)$，满足 $S$ 和 $T$ 皆纯色，且 $\operatorname{hull}(S)$ 与 $\operatorname{hull}(T)$ 不交。	定义 $\mathcal S_e$ 为 $(S, T)$ 的集合，满足删除边 $e$ 后 $S$ 和 $T$ 分别位于两个连通块中，换言之，连接 $\operatorname{hull}(S)$ 与 $\operatorname{hull}(T)$ 的路径包含边 $e$。欲求 $\vert \bigcup_{e}\mathcal S_e \vert =\sum_{e} \vert \mathcal S_e \vert -\sum_u\sum_{euf} \vert \mathcal S_e\cap\mathcal S_f \vert$。用 DSU on tree 求得点集 $U$ 中非空纯色集合的数量 $A(U)=\sum_c(2^{\#c}-1)$。对边 $e$，设删除它后得到两个连通块 $U_e$ 和 $V_e$，则 $\vert \mathcal S_e \vert =A(U_e)A(V_e)$。对相邻两条边 $e, f$，设公共点 $u$，设删除 $u$ 后得到若干连通块 $B_i$，则 $\sum_{euf} \vert \mathcal S_e\cap\mathcal S_f \vert = \sum_{i<j}A(B_i)A(B_j)$。$\mathcal{O}(N\log N)$。	AC
F	Hard	构造序列 $x$，满足 $L_i \le x_i \le R_i$。将序列 $x$ 划分为若干个连续段 $b$，使得每一段内的元素均相等，且相邻两段的元素不相等。最小化 $\sum \vert b_j \vert^2$。	(1) $f(i, x, l)$：第 $i$ 个数填 $x$，已经有相同 $l$ 个数的最小代价。 (2) 对固定的 $i$，至多保留三个互不相同 $x$。原因是转移只关心 $x \neq y$，而一个位置只有左右两个邻居，三个不同的候选值中，总能找到一个与左右邻居都不同的值。 (3) 对固定的 $i, x$，至多保留最小的两个 $l$。这是考虑到若 $l=s$ 可行且 $l= s+2$ 也可行，可以把长度 $l= s+2$ 的最后一段拆成三段 $1, 1, s$，仍合法，且代价更小。 (4) 总状态数 $\mathcal{O}(N)$，转移 $\mathcal{O}(1)$，总复杂度 $\mathcal{O}(N)$。	AC
K	Hard	有 $2N$ 张牌，数字 $1$ 到 $N$ 各两张，两人初始各持 $N$ 张。两人轮流将一张手牌置于牌堆顶。若牌堆中出现两张数字相同的牌，出牌者得 $1$ 分，并将这两张牌及其之间的所有牌移除。给定 Alice 的 $N$ 次出牌序列 $A$。求 Bob 采取最优策略时，Alice 的最小得分。	略。	AC
L	Medium	排列 $A$，定义 $A_{N+i}=\min \lbrace A_{2i}, A_{2i-1} \rbrace$。$Q$ 次操作：交换 $A_X$ 与 $A_Y$；求 $\sum_{i=L}^{R} A_{N+i}$。	修改 $A_{i}$ 只会影响 $\mathcal{O}(\log N)$ 个位置。单点修改，区间求和，$\mathcal{O}(Q\log^{2}N)$。	AC