CF1054D Changing Array 题解

· · 题解

提示 1

定义前缀异或和 s，其中 s[0] = 0，s[i] = s[i-1] \oplus a[i]。

子数组的异或和转换成 s 中两个元素的异或值。

我们需要让 s 中的不同数对尽量的多。（不同数对：数对中的两个数字不同）

提示 2

正难则反（所有数对个数减去相同数对的个数），让 s 中的相同数对尽量的少。（相同数对：数对中的两个数字相同）

提示 3

对于 a 的某个前缀，如果其中的元素修改了偶数次，那么它的前缀和不变；如果修改了奇数次，那么它的前缀和要额外异或 2^k-1。

换句话说，题目的操作相当于选择一个 s[i]（i>0），把它异或上 2^k-1。

提示 4

修改了一个 a[i]，虽然会影响后面的所有 s[j]，但 s[j] 可以通过异或 2^k-1 抵消掉修改 a[i] 所产生的影响。

因此，每个 s[i] 是互相独立的。由于求的是不同数对的数量，s[i] 在 s 中的位置是不重要的，我们只需要关心 s[i] 的出现次数。

提示 5-1

看上去用一个 map 统计 s[i] 的出现次数就行了，但是 s[i] 和 s[i] \oplus (2^k-1) 可以互相转换，如果相同的 s[i] 很多，可以转换一部分为 s[i] \oplus (2^k-1)，从而减少相同数对的个数。

提示 5-2

为了方便计算，统计 \min(s[i], s[i]\oplus (2^k-1)) 的出现次数。

设 x 出现了 \textit{cnt}[x] 次。为了让不同数对尽可能地多，应当把 \left\lfloor\dfrac{\textit{cnt}[x]}{2}\right\rfloor 个 x 异或 2^k-1，其余的 \left\lceil\dfrac{\textit{cnt}[x]}{2}\right\rceil 个 x 保持不变。

因此答案为

\binom{n}{2} - \sum_{x}\binom{\lfloor\textit{cnt}[x]/2\rfloor}{2} - \sum_{x}\dbinom{\lceil\textit{cnt}[x]/2\rceil}{2}

代码实现时，可以一边读入数组 a，一边计算 s（用一个变量）。

注

你可能会认为这样算会把 s[0] 改成 s[0]\oplus (2^k-1)。这是不会的，因为始终可以让 s[0] 在提示 5-2 的「其余的」当中。

也可以这样理解，由于 s[0] 肯定要和另外一个 s[i] 异或，就算 s[0] 变成了 s[0]\oplus (2^k-1)，也可以理解成是在 s[i] 上异或 2^k-1。

AC 代码（Go）

package main
import("bufio";."fmt";"os")

func main() {
    in := bufio.NewReader(os.Stdin)
    var n, k, v, s int
    Fscan(in, &n, &k)
    ans := c2(n + 1)
    m := 1<<k - 1
    cnt := map[int]int{s: 1} // s[0]
    for ; n > 0; n-- {
        Fscan(in, &v)
        s ^= v
        cnt[min(s, s^m)]++
    }
    for _, c := range cnt {
        ans -= c2(c/2) + c2(c-c/2)
    }
    Print(ans)
}

func c2(n int) int64 { return int64(n) * int64(n-1) / 2 }
func min(a, b int) int { if a > b { return b }; return a }