满分解法（100 分）

把前缀操作改写为增加次数

令 $c_i$ 表示位置 $i$ 总共被增加了多少次。一次操作作用于一个前缀，所以越靠前的位置被增加的次数越多或相等：

$$K\ge c_1\ge c_2\ge\cdots\ge c_n\ge 0.$$

这里 $c_1$ 就是操作总数，因为每次操作一定会增加 $a_1$。

这个条件也是充分的。令 $c_{n+1}=0$，对每个 $i$ 执行 $c_i-c_{i+1}$ 次长度为 $i$ 的前缀操作，位置 $j$ 会被所有长度不小于 $j$ 的操作覆盖，恰好增加 $c_j$。这些操作的总数为

$$\sum_{i=1}^n(c_i-c_{i+1})=c_1.$$

因此原问题等价于选择这样一个单调不增的非负整数序列，使 $(a_1+c_1)\mathbin{\&}\cdots\mathbin{\&}(a_n+c_n)$ 最大。

判定一组二进制位能否同时出现

设掩码 $M$ 表示要求答案中必须为 $1$ 的二进制位。要使最终按位与包含 $M$，每个位置的最终值 $b_i=a_i+c_i$ 都必须满足

$$b_i\mathbin{\&}M=M.$$

我们只需判断满足这些要求的最小操作数是否不超过 $K$。

由于 $c_i\ge c_{i+1}$，从右向左决定增加次数最自然。先令 $c_{n+1}=0$。已经求出 $c_{i+1}$ 时，位置 $i$ 至少要增加 $c_{i+1}$，所以它的最终值至少为

$$v=a_i+c_{i+1}.$$

记 $g(v,M)$ 为不小于 $v$ 且满足 $x\mathbin{\&}M=M$ 的最小整数。当前位置取

$$c_i=g(a_i+c_{i+1},M)-a_i.$$

这一选择不仅在当前位置最小，而且得到的是整个后缀约束下最小的 $c_i$。用归纳法说明：假设算法得到的 $c_{i+1}$ 已经不大于任意可行方案的对应增加次数 $d_{i+1}$。那么 $d_i\ge d_{i+1}\ge c_{i+1}$，且 $a_i+d_i$ 满足掩码要求。根据 $g$ 的最小性，$a_i+d_i\ge g(a_i+c_{i+1},M)$，于是 $d_i\ge c_i$。从 $i=n$ 一直推到 $1$，算法得到的 $c_1$ 就是满足 $M$ 所需的最少操作数。

所以，当且仅当最后得到 $c_1\le K$ 时，掩码 $M$ 可行。处理中一旦某个 $c_i>K$，继续向左只会需要不少于它的增加次数，可以立即判定不可行。

例如样例中要求二进制位集合 $M=5=(101)_2$。从右向左处理：$a_3=2$ 最小要变为 $5$，故 $c_3=3$；$a_2+c_3=7$ 已包含这些位，故 $c_2=3$；$a_1+c_2=4$ 最小要变为 $5$，故 $c_1=4$。这对应三次长度为 $3$ 的操作和一次长度为 $1$ 的操作。

求最小的合法整数

下面计算 $g(v,M)$。若 $v\mathbin{\&}M=M$，显然直接取 $v$。

否则，考虑 $M$ 要求为 $1$、但 $v$ 中为 $0$ 的最高二进制位 $h$。要得到不小于 $v$ 的最小合法数：

• 高于 $h$ 的各位保持与 $v$ 相同；
• 将第 $h$ 位设为 $1$；
• 低于 $h$ 的部分只保留 $M$ 强制为 $1$ 的位，其余位全部取 $0$。

第 $h$ 位从 $0$ 变为 $1$ 后，新数已经大于 $v$，所以低位可以取满足要求的最小值。若更高位比 $v$ 小，无论低位怎样选择都会小于 $v$；若更高位比 $v$ 大，又一定不如上述构造小。因此这个构造恰好是 $g(v,M)$。

代码中先计算 missing = M & ~v，其最高位就是 $h$。设高于 $h$ 的部分为 higher，低于 $h$ 且被 $M$ 要求的部分为 lower，则

$$g(v,M)=\text{higher}\mathbin{|}2^h\mathbin{|}\text{lower}.$$

从高位到低位构造答案

两个非负整数的大小由最高的不同二进制位决定。用 answer 保存已经确认能取 $1$ 的高位，从第 $60$ 位到第 $0$ 位依次尝试把当前位加入掩码。若新掩码可行，就保留这一位；否则舍弃。

在处理某一位时，更高位已经取得字典序意义下的最大选择。若当前位可行，任何不取它的结果都更小；若不可行，补充更低位也不能让当前位变得可行。因此这个逐位贪心得到最大的按位与。

因为 $a_i<2^{60}$ 且每个 $c_i\le K<2^{60}$，最终值小于 $2^{61}$，检查第 $60$ 位到第 $0$ 位已经覆盖所有可能答案。

复杂度

每次掩码判定从右向左扫描整个序列，共判定 $61$ 次，时间复杂度为 $O(61n)$。存储输入序列需要 $O(n)$ 空间，判定过程只使用 $O(1)$ 额外空间。

AC 代码（C++20）

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

i64 next_with_mask(i64 value, i64 mask) {
  i64 missing = mask & ~value;
  if (missing == 0) return value;
  int bit = 63 - __builtin_clzll(static_cast<unsigned long long>(missing));
  i64 lower = bit == 0 ? 0 : mask & ((1LL << bit) - 1);
  i64 higher = value >> (bit + 1) << (bit + 1);
  return higher | (1LL << bit) | lower;
}

void solve() {
  int n;
  i64 k;
  cin >> n >> k;
  vector<i64> a(n);
  for (i64 &x : a) cin >> x;

  auto check = [&](i64 mask) {
    i64 added = 0;
    for (int i = n - 1; i >= 0; --i) {
      i64 value = next_with_mask(a[i] + added, mask);
      added = value - a[i];
      if (added > k) return false;
    }
    return true;
  };

  i64 answer = 0;
  for (int bit = 60; bit >= 0; --bit) {
    i64 candidate = answer | (1LL << bit);
    if (check(candidate)) answer = candidate;
  }
  cout << answer << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

不进行操作时直接求按位与（通过子任务 8–9，共 8 分）

当 $K=0$ 时不能进行任何操作，最终序列与输入完全相同。因此只需从左到右把所有 $a_i$ 做按位与，所得值就是唯一可能的答案。

时间复杂度为 $O(n)$，只保存当前按位与结果，额外空间复杂度为 $O(1)$。

参考代码（C++20）

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

void solve() {
  int n;
  i64 k;
  cin >> n >> k;
  i64 answer;
  cin >> answer;
  for (int i = 1; i < n; ++i) {
    i64 value;
    cin >> value;
    answer &= value;
  }
  cout << answer << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

枚举各位置的增加次数（通过子任务 1–9，共 36 分）

在 $n\le7$、$K\le8$ 时，可以直接枚举每个位置的增加次数 $c_i\in[0,K]$。

一次前缀操作会增加第一个位置，并且覆盖靠后位置的操作一定也覆盖靠前位置，所以合法的增加次数必须满足

$$c_1\ge c_2\ge\cdots\ge c_n.$$

反过来，这个条件足以保证方案能由前缀操作实现：令 $c_{n+1}=0$，执行 $c_i-c_{i+1}$ 次长度为 $i$ 的操作即可。操作总数为 $c_1\le K$。

枚举一个完整的 $c$ 序列后，先检查上述单调关系；若合法，就计算所有 $a_i+c_i$ 的按位与并更新最大值。共有 $(K+1)^n$ 个候选，每个候选需要 $O(n)$ 时间检查和计算，因此时间复杂度为 $O(n(K+1)^n)$，空间复杂度为 $O(n)$。

当 $K=0$ 时只有一个候选增加次数序列，所以这份程序也能在线性时间内通过测试点 $8\sim9$。

参考代码（C++20）

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

void solve() {
  int n;
  i64 k;
  cin >> n >> k;
  vector<i64> a(n), added(n);
  for (i64 &x : a) cin >> x;

  i64 answer = 0;
  while (true) {
    bool valid = true;
    for (int i = 1; i < n; ++i) {
      if (added[i - 1] < added[i]) {
        valid = false;
        break;
      }
    }
    if (valid) {
      i64 value = a[0] + added[0];
      for (int i = 1; i < n; ++i) value &= a[i] + added[i];
      answer = max(answer, value);
    }

    int position = n - 1;
    while (position >= 0 && added[position] == k) {
      added[position] = 0;
      --position;
    }
    if (position < 0) break;
    ++added[position];
  }
  cout << answer << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}