题解：CF1344F Piet's Palette
zhenjianuo2025
·
·
题解
题解区似乎没看到这种做法，所以发个题解。
一个熟知的事实 1\oplus 2\oplus 3=0。
考虑将 RBY 标号为 123，空白标号为 0。设 01 变量 x_{i,1/2/3} 表示 i 上的颜色是否为 1/2/3。RY RB YB 操作显然都是对三种颜色的对换，对换复合能得到任意的置换。所以不妨直接维护出每个位置的置换是什么。
考虑列出 mix 操作对应的方程。拆成高低两位各列一个方程，对于低位列出 \oplus_{i\in S,1\le j\le 3}([p_{i,j}=1]+[p_{i,j}=3])x_{i,j}=c_0，对于高位同理，\oplus_{i\in S,1\le j\le 3}([p_{i,j}=2]+[p_{i,j}=3])x_{i,j}=c_1。
最后考虑对每个 x_{i,1},x_{i,2},x_{i,3} 中最多有一个 1 的限制。直接限制 x_{i,1}\oplus x_{i,2}\oplus x_{i,3}=1，如果 x_{i,1}=x_{i,2}=x_{i,3}=1，将 i 的颜色调整为空即可。
最后需要解一个 \mathbb F_2 意义下的方程组（需要注意系数矩阵可能不满秩）。复杂度为 O\left(\frac{n(n+k)^2}{w}\right)。