260228A. 典

长为 \(m\) 的序列 \(a\) 的权值为 \(W(a)=a_1+\left(\displaystyle\sum_{i=1}^{m-1}a_i\oplus a_{i+1}\right)+a_m\)。

给定一个长为 \(n\) 的序列 \(a\)，你可以选择任意多个数修改为任意值。

最小化 \(pC+W(a')\)，其中 \(a'\) 为最终的序列，\(p\) 为选择个数，\(C\) 为给定常量。

\[n\le2\times10^5,a_i\le2^{18} \]

---

\(2^{18}\approx2.6\times10^5\)，所以 \(n\) 与 \(V\) 同阶。

首先注意到，修改一个数等价于删去它。总是把选中的数改为与其前驱相同即可。

那么问题转化为求 \(a\) 的一子序列 \(b\) 最小化 \((n-|b|)C+W(b)\)，即最小化 \(W(b)-|b|C\)。

考虑一个 dp，设 \(f_i\) 表示 \(b\) 以 \(a_i\) 结尾的最小代价，显然有转移：

\[f_i=\min_{j<i}f_j+a_j\oplus a_i-C \]

把下标放到值域上，我们需要维护这样的东西：

\[f_u=\min f_v+u\oplus v \]

一种方法是使用高低位分块优化，令 \(H(x)\) 表示 \(x\) 的高 \(9\) 位，\(L(x)\) 表示 \(x\) 的低 \(9\) 位。

设辅助数组 \(g_{x,y}\) 表示所有高 \(H(v)=y\) 的 \(v\) 中，\(f_v+L(v)\oplus x\) 的最小值。

更新 \(f_v\) 时只需枚举 \(x\) 更新，求解 \(f_u\) 时只需枚举 \(y\) 计算 \(g_{L(u),y}+H(x)\oplus y\) 的最小值。

复杂度 \(\mathcal O(n\sqrt V)\)。

第二种方法是注意到上式换元可得：

\[f_{u\oplus v}=\min f_v+u \]

相当于是 \(f\) 和 \(id\) 的 (min,xor) 卷积。由于 \(id\) 满足位独立可加性，我们可以用一种 FWT 变体解决。

具体地，枚举第 \(d\) 位上的每一对数 \(f^-,f^+\)，更新 \(f^-=\min(f^-,f^++2^d)\)，\(f^+\) 同理。

那么我们分块，每块做一次 FWT，块内暴力转移，可以平衡到 \(\mathcal O(n\sqrt{V\log V})\)。

code

#include <algorithm>
#include <iostream>
const int N = (1 << 18);
typedef long long i64;
const i64 inf = 1e18;i64 w[N];
inline void work() {for(int j = 1; j < N; j <<= 1) {for(int i = 0; i < N; ++i) {w[i] = std::min(w[i], w[i^j] + j);}}
}i64 C, dp[N];
int n, v[N];
const int B = 1800;
inline void solve() {std::cin >> n >> C; for(int i = 1; i <= n; ++i) std::cin >> v[i];for(int i = 1; i < N; ++i) w[i] = inf;w[0] = dp[0] = -C, v[n + 1] = 0;for(int l = 1; l <= n + 1; l += B) {int r = l + B - 1;work();for(int i = l; i <= r; ++i) {dp[i] = w[v[i]];for(int j = l; j < i; ++j) {dp[i] = std::min(dp[i], dp[j] + (v[i] ^ v[j]));}dp[i] -= C;w[v[i]] = std::min(w[v[i]], dp[i]);}}std::cout << dp[n+1] + C*(n+2) << "\n";
}int main() {std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);int t; std::cin >> t; for(; t--; ) solve();
}