题解 - AGC071A XOR Cross Over

变身喜欢降降降的小朋友。评分系统我问你，A、B、C 真的是同一个紫吗？

简述题意

给一个数列 $\{a_1,\ldots,a_n\}$。每次可以选择一个长度不为 $1$ 的数列拆成非空的两半：$\{a_1,\ldots,a_{k-1}\}$ 和 $\{a_k,\ldots,a_n\}$，然后每个元素都异或上另一半的异或和。最小化这样拆分 $n-1$ 次后的元素和。$n\le 500,a_i< 2^{40}$。

追踪

关注一下这个过程中值的变化。比如说现在有一个数列，根据题意，它们在以前被异或的总和是相同的，假设叫做 $t$。再稍微假设一下分裂成的两半的原始数分别是 $\{a_1,\ldots,a_n\}$ 和 $\{b_1,\ldots,b_m\}$，就是说它们现在的值分别是 $\{a_1\oplus t,\ldots,a_n\oplus t\}$ 和 $\{b_1\oplus t,\ldots,b_m\oplus t\}$。令 $B=\oplus_{1\le i\le m} b_i$，我们追踪 $a$ 中元素的变化（$b$ 为对称的情况）：

• $m$ 是偶数时，$a_i\oplus t$ 变为 $a_i\oplus B\oplus t$。
• $m$ 是奇数时，$a_i\oplus t$ 变为 $a_i\oplus B$。

刻画

把分裂的过程画成线段树，$a_i$ 现在的值是：找到其祖先中最低的，令其为 $a'$，满足 $a'$ 的兄弟长度为奇数，$a_i$ 现在的值即为 $a'$ 父亲区间的异或和。

或者，不如说：找到其祖先中最低的，令其为 $a'$，满足 $a'$ 的长度为偶数，$a_i$ 现在的值即为 $a'$ 区间的异或和。

如果不存在 $a'$，必然有 $n$ 是奇数，手动模拟发现 $a_i$ 现在的值是整个序列的异或和，我们称它为“特殊点”。

区间 DP

令 $f(l,r)$ 表示把 $[l,r)$ 中的区间拆到一个线段树节点下，最小的元素和。对于长为奇数的区间，不计入“特殊点”，因为它会被更新。边界情况是长度为 $f(i,i+1)=0$。

枚举分界点 $k$。

• 两个子树均为奇数长：$f(l,r)\leftarrow f(l,k)+f(k,r)+2S$，其中 $S$ 表示 $[l,r)$ 区间的异或和。
• 否则：$f(l,r)\leftarrow f(l,k)+f(k,r)$。

最后输出时处理全局中的“特殊点”。

时间复杂度 $O(n^3)$。

代码

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MXN = 505;
const ll INF = 1LL << 62;
int N;
ll arr[MXN], pfs[MXN];
ll mns[MXN][MXN];

int main() {
  cin >> N;
  for (int i(0); i != N; ++i) cin >> arr[i], pfs[i + 1] = pfs[i] ^ arr[i];
  for (int len(2); len <= N; ++len) {
    for (int l(0); l + len <= N; ++l) {
      int r(l + len);
      ll s(pfs[r] ^ pfs[l]);
      mns[l][r] = INF;
      for (int i(l + 1); i != r; ++i)
        mns[l][r] = min(mns[l][r], mns[l][i] + mns[i][r] +
            ((i - l) % 2 + (r - i) % 2 == 2 ? (2 * s) : 0LL));
    }
  }
  cout << mns[0][N] + (N & 1 ? pfs[N] : 0LL) << endl;
  return 0;
}