2025.2做题记录

Codeforces Round 1078 Div2

F2. Again trees...(Hard Version)

题意：问将树划分成若干连通块的方案树，要求满足每个连通块的点权异或和 \(\in B\)。\(n\le 10^5,\ |B|=k\le 10\)，点权 \(\le 2^{30}\)。

设计 dp 状态 \(f_{u, s}\) 表示 \(u\) 子树中不属于 \(u\) 连通块部分的异或和为 \(s\)。由于 \(s\) 一定为 \(B\) 某个子集的异或和，合法 \(s\) 的数量不超过 \(2^k\)。

可以找出 \(B\) 的一组异或线性基将状态压平。下称 \(R(s)\) 为 \(s\) 线性基的子集 \(s\) 异或和对应的真实值。下文左箭头表示 +=。

先枚举儿子 \(v\) 转移

\[f'_{u, s\oplus t} \leftarrow f_{u,s}\times g_{v,t} \]

记 \(sxor_u\) 表示 \(u\) 子树异或和。
检查自己能否作为一个连通块最靠近根的点。记 \(sxor_u\) 在线性基下表示为 \(t\)。

\[f_{u, t}\leftarrow \sum_{s,R(s)\oplus sxor_u\in B} f_{u,s} \]

在根节点处统计答案即可。这样的转移是 \(O(n2^{2k})\) 的，可以通过 F1。复杂度瓶颈在异或卷积。我们维护 \(f_u\) 的异或 FWT 数组，记为 \(fwt(u)\)。这样我们可以 \(O(2^k)\) 计算一次卷积。

现考虑第二个转移式，它包含一个多点求和和一个单点修改。

记求和式中满足要求的 \(s\) 构成集合 \(V\)。

由异或 FWT 的性质，\(FWT(fwt_u)=2^kf_u\)。

故 \(\sum_{s\in V}f_{u,s}=\sum_{s\in V}FWT(fwt_{u,s})\)。

记 \(a\circ b=\text{popcount}(a\cap b) \bmod 2\)，上式即：

\[\begin{align*} &\sum_{s\in V}\sum_{i=0}^{2^k-1} (1-2[s\circ i])fwt_{u,i} \\ =&\sum_{i=0}^{2^k-1}fwt_{u,i}(|V| -2\sum_{s\in V} [s\circ i]) \end{align*} \]

扫描 \(i\) 求和，\(i\to i+1\)，对于改变的每一个 bits，反转对应的那些 \(s\)（即该位为 \(1\) 的）的 \([s \circ i]\)。

由于 \(\sum_{i=1}\text{popcount}(i \oplus (i+1))\) 是线性的，所以直接这样做时间复杂度就是正确的。同时，另一个事实是 \(i \to i+1\) 改变的 bits 是一个前缀，所以我们可以预处理每个前缀会改变的 \(s\) 的集合。

对 \(f_{u, t}\) 的修改暴力即可。故总时间复杂度为 \(O(n2^k)\)。

Codeforces Round 1079 Div1 & Div2

D. Double Bracket Sequence

题意：给定一个由 ()[] 四种字符组成的串 \(s\)，每次操作可以将任意位置修改成四种字符之一。询问最少的操作次数使得圆括号和方括号部分分别构成合法匹配。\(|s|\le 10^6\)。

一定存在保留原有圆、方括号最大匹配的最优方案。不匹配的左括号取更靠右的不劣，不匹配的右括号取更靠左的不劣。故我们找失配方案中括号最靠近中心的。可以通过栈匹配构造，去掉匹配的部分，记剩余部分为 \(t\)，一定有 \(|t|\) 为偶数。最理想的情况下，我们可以花 \(|t|/2\) 的代价两两匹配。

当 \(t\) 中存在 [) 或 (]，一定可以做到 \(|t|/2\)。

否则 \(t\) 形如 \(a\) 个右括号拼上 \(b\) 个左括号。当 \(a,b\) 为偶数时，相邻两个匹配可以做到 \(|t|/2\)，否则为 \(|t|/2+1\)。

E1. Fuzzy Concatenation (Easy Version)

题意：给定一个串 \(s\)。\(s\) 生成一个串的规则是每次取 \(s\) 的一个子串，可将该子串某个位置修改成任意字符，再将该子串拼接到生成串尾部。问 \(t\) 由 \(s\) 生成最少需要多少上述过程。

\[|s|=n\le 10^5,|t|=m\le 10^4 \]

对于 Hard Version，

\[|s|=n\le 5\times 10^5,|t|=m\le 5\times 10^4 \]

贪心地每次取一段 \(t\) 能由 \(s\) 生成的前缀是最优的。

考虑模拟该贪心的过程。考虑在 \(t\) 上的位置 \(p\)。建立 \(s\) 的 SAM，在 s 上匹配 \(t\) 从 \(p\) 开始的后缀。然后枚举断点位置，枚举修改字符，再继续匹配。

该过程总复杂度 \(O(26m^2)\)。我们可以为如上的暴力匹配过程设置一个界 \(L\)。记上述从 \(p\) 开始能走到的最大位置为 \(q\)。当 \(q-p+1=L\)，停止暴力匹配。这时我们直接枚举 \(s\) 每个位置，求其和 \(t\) 的 LCP，在跳过不一样的一位，再求 LCP。求两串 LCP 可以做到线性。

复杂度分析：暴力匹配部分设停止时 \(q-p+1=B, B\le L\)。该部分为

\[\sum_{B_i}26B_i^2\le 26L(\sum_{B_i} B_i)\le 26mL \]

枚举 \(s\) 位置匹配单组复杂度 \(O(n)\)，该部分为 \(\displaystyle\frac{nm}{L}\)。

故总复杂度为

\[O(26mL+\frac{nm}{L}) \]

ps. 我觉得理论上有可能过 E2。