题解：P14759 [Opoi 2025] CCD 的异或 II
SuyctidohanQ
·
·
题解
题目要求构造长度为 n 的 01 序列 A，满足 m 个限制：区间 [l, r] 的异或和为 1。可以转化为前缀异或和 S 的问题，其中 S_i = A_1 \oplus A_2 \oplus \dots \oplus A_i，并规定 S_0 = 0。
每个限制 (l, r) 等价于 S_{l-1} \ne S_r。我们可以将每个限制看作在 l-1 和 r 之间连一条无向边，表示这两个点的 S 值不能相同。
首先判断是否有解。如果图不是二分图，则存在奇环，必然会导致矛盾，此时方案数为 0。
如果图是二分图，那么每个连通块内部的点被分为两个集合，同一个集合内的 S 值相同。每个连通块有两种染色方案（将某个集合染为 0，另一个染为 1）。但由于 S_0 固定为 0，所以包含点 0 的连通块只有一种方案。设连通块总数为 k，则方案数为 2^{k-1}。
对于字典序最小的构造，我们需要还原出原序列 A。由于 A_i = S_i \oplus S_{i-1}，要让 A 的字典序最小，应尽可能让 A_i = 0，即让 S_i = S_{i-1}。因此，在确定每个点的 S 值时，如果该点所在连通块尚未确定，就令该点的 S 值与上一个点的 S 值相同。这样贪心即可得到字典序最小的 A。