做题记录 25.10.17

szt100309 · 2025-10-17 07:34:54 · 个人记录

\textcolor{black}\odot AT_agc027_e [AGC027E] ABBreviate

设最终将 s 缩为字符串 t，则 t 的每个字母对应 s 的一个区间，即 s 对应区间可以缩为一个字母，考虑怎样的字符串可以缩为一个字母

令 \text a 为 1，\text b 为 2，在 \bmod 3 意义下求前缀和，显然题目的操作不改变整个字符串 \bmod 3 意义下的总和，因此若一个字符串 \bmod 3 下和为 0，则必然不能缩为一个字母

显然字符串 \text a\text b 交错时也不能缩为一个字母（除非初始长度就是 1）

定理 \text 1：对于 n=|s|>1 的 s，若 \sum_i (1+[s_i=\text b])\equiv 0\pmod 3 且存在 1\le k<n 使得 s_k=s_{k+1}，则 s 必然可以缩为一个字母

证明：

不妨设 s_k=s_{k+1}=\text a 且 k 为第一个合法位置
当 |s|=2 时显然
否则若 k=1 且合并 s_k 与 s_{k+1} 后无法进一步操作，说明初始 s_{1\sim 3}=\text a 导致合并后为 \text b\text a\cdots，因为总和 \bmod 3 不为 0，因此 |s|>3，又合并 s_{1\sim 2} 后无法进一步操作，因此 s_4=\text b，此时可以选择合并 s_2 和 s_3，合并之后前缀为 \text a\text b\text b，可以进一步操作
若 1<k\le n-1 且合并后无法进一步操作，则说明 s_{k-1\sim k+1}=\text a，此时 k 不是第一个合法位置，不满足前提
综上，若存在 1\le k<n 满足条件，则一定存在操作方案使得 |s| 减一后仍然存在 0\le k<|s| 满足条件，因此可以反复合并直到长度为 1，即缩为一个字母

显然最终得到的字母与初始的字符串总和 \bmod 3 相同，若初始串总和 b\bmod3 为 1 则缩为 \text a，若为 2 则缩为 \text b

因此对于一个字符串，无论是否满足存在相邻相同字符，其理论上能缩到的字符都是确定的

特判初始的 s 就是 \text a\text b 交替的情况，显然此时答案为 1

定理 \text 2：假设在不满足存在相邻相同字符的情况下 s 缩为 t，则一定存在合法的操作方法同样能得到 t

证明：

假设得到 t 的过程中 s 划分为 [l_i,r_i]\mid 1\le i\le m
若存在 [l_k,r_k] 使得 s_{l_k\sim r_k} 中不存在相邻相同字符
若 l_k=r_k 则其合法
否则若 k<m，则必然有 \sum_{i=l_k}^{r_k}(1+[s_i=\text b])\not\equiv 0\pmod 3，不妨设缩为 \text a，则 r_k-l_k+1 必然为奇数且 s[l_k:r_k]=\text{abab}\cdots\text{aba}，此时显然可以保留 \text a 而把剩下的 (\text{ba})^k 移到下一段，显然该过程不改变最终得到的 t 且使 [l_k,r_k] 合法
若 k=m，则向前面移动，显然不是 \text a\text b 交替的 s 串的划分中，前面一定存在一个合法的段使得向前移动的过程中止

令 p_i=\sum_{j=1}^i (1+[s_j=\text b])\bmod 3，则转化为每次可以选择一个 [l,r] 满足 p_r\ne p_{l-1}，将 s[l:r] 替换为 (p_r-p_{l-1})\bmod 3

令 f_i 表示 [1,i] 的答案，令 pr_{i,j} 表示 [1,i) 中最后一个 p_x=j 的 x，不存在则为 0，则 f_i=[p_i\ne 0]+\sum_{c=0}^2[p_i\ne c]f_{pr_{i,c}}，正确性显然

时间复杂度 O(n)

代码

参考

显然 s_{1\sim n} 中 1\sim n 开头的分别有恰好一个，t_{1\sim n} 中 1\sim n 开头的分别有恰好一个，即 s\cup t 中 1\sim n 开头的分别有恰好两个，因此排名 2i-1 和 2i 的必然都以 i 开头

显然 2i-1 和 2i 不能同时属于 a 或 b，特判这种情况答案为 0

令初始第 i 个序列中间一项为 c_i

显然若 a_x=2i-1,b_y=2i 则 c_x<c_y，反之若 a_x=2i,b_y=2i-1 则 c_x>c_y

令小的 c 向大的连边，对于确定的 b，显然得到的图视为无向图后所有连通块都是环，若存在有向环则无解

考虑重排所有 (a_i,b_i)\mid_{i=1}^n，使得 \left\lceil \frac{a_i}2\right\rceil=i，设此时 \left\lceil\frac{b_i}2\right\rceil=p_i（若 b_i=-1 则 p_i=-1）

则 i\to p_i 当且仅当 2\mid a_{p_i}，i\gets p_i 当且仅当 2\nmid a_{p_i}

要求不能有一个环内方向都相同，即要求一个环内 a_{p_i} 奇偶性不完全相同

遍历所有已经确定的环，若存在奇偶完全相同则答案为 0

去掉环后剩余若干链，设其中 2\mid a_{p_i} 的有 c_0 条，2\nmid a_{p_i} 的有 c_1 条，二者兼有的有 c_2 条

转化为 c_0 个红色点，c_1 个蓝色点，c_2 个双色点，要将它们组合为若干环，使得不存在一个环为同色的

考虑容斥，钦定有 k 个红色环，它们由 i 个红色点组成，钦定有 l 个蓝色环，它们由 j 个蓝色点组成，显然容斥系数为 (-1)^k (-1)^l

令 g_{i,j} 表示 i 个点组成 j 个环的方案数，则答案为

\sum_i\sum_j\sum_k\sum_l \binom{c_0}i\binom{c_1}j(-1)^k(-1)^l g_{i,k}g_{j,l} (c_0+c_1+c_2-i-j)!

其中 (c_0+c_1+c_2-i-j)! 表示剩余 c_0+c_1+c_2-i-j 个点任意成环的方案数

令 f_i=\sum_j (-1)^j g_{i,j} 表示所有长度为 i 的排列 p 的 (-1)^{s(p)} 之和，其中 s(p) 表示 p 的置换环数量，则答案为

\sum_i\sum_j \binom{c_0}i\binom{c_1}jf_if_j (c_0+c_1+c_2-i-j)!

可证 f_0=1,f_1=-1,f_{ge 2}=0，因此答案可 O(1) 算出

总时间复杂度 O(n)

代码

参考