2026-10-28：加法与取模博弈的 Baby / Easy 解法

适用范围：$n\le 5000$、$1\le A_i\le 1000$、$0\le X_0\le 10^9$。这是助手推导与编写的参考解法，采用二分答案、布尔博弈 DP 和位集并行；另加精确的周期压缩。文末给出本地验证情况。

先看 $X_0=5$、$A=[3,4]$。A 如果加 $3$，B 随后取模得到 $0$；A 如果取模得到 $2$，B 的最优结果则是 $2$。所以答案是 $2$。这说明需要对后续博弈逆推，不能只比较眼前的两个数。

若 $n=1$，答案直接是 $X_0+A_1$。下面考虑 $n\ge 2$。

最后一个 A 回合必然选择加法。如果 $n$ 为奇数，可以删去这一回合，并在最后给答案加上 $A_n$。剩下的操作数记为 $m$，它是偶数。记 $b=A_m$，此时最后由 B 操作，B 必然选择取模，所以剩余游戏的结果在 $[0,b-1]$ 内。

二分这个剩余结果。对于阈值 $K$，令 $D_i(t)$ 表示：已经执行前 $i$ 步、当前数字为 $t$ 时，A 能否保证最终数字至少为 $K$。

A 只需两个选项中至少一个能成功，B 则会在存在失败分支时选择它。因此

$$ D_{i-1}(t)= \begin{cases} D_i(t+A_i)\lor D_i(t\bmod A_i),&i\text{ 为奇数},\\ D_i(t+A_i)\land D_i(t\bmod A_i),&i\text{ 为偶数}. \end{cases} $$

直接从最后的 B 回合之前开始逆推：

$$ D_{m-1}(t)=[t\bmod b\ge K]. $$

这一布尔函数以 $b$ 为周期。二分的判定单调，因为“能保证至少 $K$”成立时，对所有更小的阈值也成立。

大初始值只需要一个额外状态。令 $S_i=\sum_{j=1}^i A_j$。执行完前 $i$ 步后：

• 如果一直加法，当前值恰好为 $H_i=X_0+S_i$。
• 如果最后一次取模发生在第 $j$ 步，设当时余数为 $r$，则当前值为 $r+S_i-S_j$，其中 $0\le r < A_j$。于是当前值至多是 $S_i-S_{j-1}-1\le S_i-1$。

所以每一层只需维护 $[0,S_i-1]$ 内的状态，加上一个单独的 $H_i$ 状态。允许在小区间中计算实际不可达的状态，因为转移在这些区间内闭合，不会改变所求初始状态的值。

记 $h_i=D_i(H_i)$，它的加法分支就是 $h_i$，取模分支则从小区间查询：

$$ h_{i-1}=h_i\mathbin{\mathrm{op}}D_i\bigl((X_0+S_{i-1})\bmod A_i\bigr), $$

其中 $\mathrm{op}$ 在 A 回合为 OR，在 B 回合为 AND。最后要求的判定结果就是 $h_0$。因此初始 $X_0$ 再大也不会扩大位集。

对小区间，把 $D_i(0),D_i(1),\ldots$ 存成位集。转移中的加法分支相当于读原位集从第 $A_i$ 位开始的后缀；取模分支是把前 $A_i$ 位反复复制。于是整层转移可以用 64 位整数一次处理 64 个状态。

设 $a=A_i$。每个输出字的取模掩码从 $64j\bmod a$ 开始，掩码序列只有 $a/\gcd(a,64)$ 个字的周期。先用 $O(a)$ 时间准备这组掩码，整层就只需按字执行 OR 或 AND。实现中在源周期和掩码周期的边界处切块，使内层循环读取连续数组；不在每个字上做除法或取模。

参考实现还用了三个保持精确性的优化：

• 若当前布尔函数已知有周期 $p$，新函数一定以 $\operatorname{lcm}(p,A_i)$ 为周期，因为加法分支以 $p$ 为周期，取模分支以 $A_i$ 为周期。当这个周期比所需前缀短时，只保存一个完整周期。周期不必最小。当 $A_i$ 为 $p$ 的倍数时，两种操作得到的布尔值都等于当前函数在原位置的值，可以直接跳过这一层。
• 若模分支的全部 $A_i$ 个值相同：该值是当前玩家希望得到的布尔值时，整层成为常量，可以结束判定；否则只剩加法分支，只需移动数组起点或周期内的旋转位置。
• 先除去所有有效 $A_i$ 的最大公约数 $g$。写 $X_0=gq+r$，所有操作都保持余数 $r$，原游戏等价于对 $q$ 和 $A_i/g$ 进行游戏，最后还原为 $r+g\cdot\mathrm{answer}$。已经删去的最后一个 A 回合作为独立常量再加回来。

令 $M=\max A_i$、$S=\sum A_i$、机器字长 $w=64$。每次判定最坏需要

$$ O\left(S+\sum_{i=1}^{m-1}\left\lceil\frac{S_i}{w}\right\rceil\right) $$

时间，二分后可以写为

$$ O\left(\left(nM+\frac{n^2M}{64}\right)\log(M+1)\right). $$

空间为 $O(n+M+S/64)$ 个机器字，包含数组、两份滚动位集、掩码和常数级调用栈。$n=5000,M=1000$ 时，两份位集缓冲区合计约 $1.2\,\mathrm{MiB}$。周期压缩和提前结束只会减少上述计算量；这里给出的最坏界仍然关于 $n$ 是二次的。

C++17 参考实现：

#include <algorithm>
#include <cstdint>
#include <numeric>
#include <vector>
#include <utility>

class Game_solver {
    using U64 = std::uint64_t;
    std::vector<int> a;
    long long x;
    int n, sum;
    std::vector<U64> f, g;

    // Read a bit or 64 consecutive bits; the buffer has padding at its end.
    static bool bit(const std::vector<U64> &v, int p) {
        return (v[p >> 6] >> (p & 63)) & 1;
    }
    static U64 word(const U64 *v, int p) {
        int q = p >> 6, r = p & 63;
        if (r == 0) return v[q];
        return (v[q] >> r) | (v[q + 1] << (64 - r));
    }
    static void pad(std::vector<U64> &v, int p) {
        // Append the next 64 bits of this cyclic sequence.
        for (int i = 0, r = 0; i < 64; ++i) {
            int t = p + i;
            U64 mask = U64(1) << (t & 63);
            if (bit(v, r)) v[t >> 6] |= mask;
            else v[t >> 6] &= ~mask;
            if (++r == p) r = 0;
        }
    }

    bool win(int k) {
        // Initially, the last B move takes modulo b.
        int b = a.back(), len = sum - b, period = b, origin = 0;
        bool high = (x + len) % b >= k;
        std::fill(f.begin(), f.end(), 0);
        for (int r = k; r < b; ++r) f[r >> 6] |= U64(1) << (r & 63);
        pad(f, period);

        for (int i = n - 2; i >= 0; --i) {
            // period == 0: store the relevant prefix at offset origin.
            // period > 0: store a full period, with rotation origin.
            int d = a[i];
            len -= d;
            bool is_max = i % 2 == 0;
            // Both operations preserve a periodic function when period divides d.
            if (period && d % period == 0) continue;

            // The modulo branch repeats these d low-state bits.
            U64 seed[34] = {}, masks[1001];
            int ones = 0, p = origin;
            for (int r = 0; r < d; ++r) {
                bool v = bit(f, p);
                ones += v;
                if (v) seed[r >> 6] |= U64(1) << (r & 63);
                ++p;
                if (period && p == period) p = 0;
            }
            int r_high = (x + len) % d;
            // The unique state reached by taking addition at every earlier step.
            bool small = (seed[r_high >> 6] >> (r_high & 63)) & 1;
            high = is_max ? high || small : high && small;
            if (len == 0) return high;
            if ((is_max && ones == d) || (!is_max && ones == 0)) return is_max;

            // A uniform unfavorable modulo branch leaves only the addition branch.
            if (ones == 0 || ones == d) {
                origin += d;
                if (period) origin %= period;
                continue;
            }
            for (int t = 0, r = 0; t < 64; ++t) {
                if ((seed[r >> 6] >> (r & 63)) & 1) {
                    int pos = d + t;
                    seed[pos >> 6] |= U64(1) << (pos & 63);
                }
                if (++r == d) r = 0;
            }
            int count = d / std::gcd(d, 64), step = 64 % d, r = 0;
            // The repeated d-bit string has count different aligned 64-bit words.
            for (int j = 0; j < count; ++j) {
                masks[j] = word(seed, r);
                r += step;
                if (r >= d) r -= d;
            }

            int new_period = 0, out_len = len;
            // Preserve an exact period only while storing it saves space and work.
            if (period) {
                long long lcm = 1LL * (period / std::gcd(period, d)) * d;
                if (lcm <= len) new_period = out_len = int(lcm);
            }
            int words = (out_len + 63) >> 6;
            int src = origin + d;
            if (period) src %= period;
            // Split at source/mask wrap points, then combine contiguous word ranges.
            for (int j = 0, z = 0; j < words; ) {
                int take = std::min(words - j, count - z);
                if (period) take = std::min(take, (period - src + 63) / 64);
                int q = src >> 6, shift = src & 63;
                if (is_max) {
                    if (shift) {
                        for (int t = 0; t < take; ++t)
                            g[j + t] = ((f[q + t] >> shift) | (f[q + t + 1] << (64 - shift))) | masks[z + t];
                    } else {
                        for (int t = 0; t < take; ++t) g[j + t] = f[q + t] | masks[z + t];
                    }
                } else {
                    if (shift) {
                        for (int t = 0; t < take; ++t)
                            g[j + t] = ((f[q + t] >> shift) | (f[q + t + 1] << (64 - shift))) & masks[z + t];
                    } else {
                        for (int t = 0; t < take; ++t) g[j + t] = f[q + t] & masks[z + t];
                    }
                }
                j += take;
                z += take;
                if (z == count) z = 0;
                src += 64 * take;
                if (period && src >= period) src %= period;
            }
            f.swap(g);
            origin = 0;
            period = new_period;
            if (period) pad(f, period);
        }
        return high;
    }

public:
    Game_solver(std::vector<int> values, long long initial) : a(std::move(values)), x(initial) {
        n = int(a.size());
        sum = std::accumulate(a.begin(), a.end(), 0);
        int size = (std::max(sum, 1000) + 255) / 64 + 4;
        f.resize(size);
        g.resize(size);
    }
    int solve() {
        int lo = 0, hi = a.back() - 1;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (win(mid)) lo = mid;
            else hi = mid - 1;
        }
        return lo;
    }
};

inline long long solve_game(std::vector<int> a, long long x) {
    if (a.size() == 1) return x + a[0];
    long long bonus = 0;
    if (a.size() % 2) {
        bonus = a.back();
        a.pop_back();
    }
    int d = 0;
    for (int v : a) d = std::gcd(d, v);
    long long remainder = x % d;
    // Every operation preserves x modulo the common divisor.
    x /= d;
    for (int &v : a) v /= d;
    return bonus + remainder + d * Game_solver(std::move(a), x).solve();
}

#include <iostream>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    long long x;
    std::cin >> n >> x;
    std::vector<int> a(n);
    for (int &v : a) std::cin >> v;
    std::cout << solve_game(std::move(a), x) << '\n';
}