2025 ICPC AsiaEC Shanghai

D

我们直接枚举 $3^n$ 个 mask (i.e., $0,1,\texttt{?}$ )

考虑 mask 的第 $n$ 位，如果是 $0,1$ ，那么剩下的其实就是大小为 $n-1$ 的一个子问题；比较麻烦的是当这一位取 $\texttt{?}$ 的时候。

我们让子问题的解为 $S=\texttt{umap}[M,A], M\in [0, 3^{n-1})$ ，其中的 $A$ 表示 mask $M$ 可以匹配的 $a_{i}$ 之和，我们既然可以知道第 $n$ 位分别是 $0,1$ 时的解，那么根据

\texttt{?}M=\texttt{1}M+\texttt{0}M

我们就可以计算当前位取 $?$ ，其余 $n-1$ 位为 $M$ 时候的解为 $S_{?}[M]=S_{1}[M]+S_{0}[M]$

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

Problem D

#include <cassert>
#include <cmath>
#include <iostream>
#include <vector>

constexpr int M = 43046721;

int main() {
  int n;
  std::cin >> n;
  std::vector<int> a(1 << n);
  for (auto &x : a)
    std::cin >> x;

  int ans = 0;
  auto F = [&](auto f, int p, int prefix) -> std::vector<int> {
    if (p == 0) {
      ans ^= a[prefix];
      return {a[prefix]};
    }

    // suppose 1 on this bit
    auto l = f(f, p - 1, prefix << 1 | 1);
    // suppose 0 on this bit
    auto r = f(f, p - 1, prefix << 1);

    assert(l.size() == r.size());
    assert(l.size() == std::pow(3, p - 1));

    int sum = 0;
    std::vector<int> ret;
    for (int i = 0; i < l.size(); i++) {
      ans ^= l[i] + r[i];
      ret.push_back(l[i] + r[i]);
    }
    for (auto i : l)
      ret.push_back(i), sum += i;
    for (auto i : r)
      ret.push_back(i), sum += i;

    return ret;
  };

  F(F, n, 0);
  std::cout << ans << "\n";
}