[ABC297G] Constrained Nim 2 题解

标签：right cdot 题解 ABC297G le Constrained SG operatorname left

题意

有 \(N\) 堆石子，其中第 \(i\) 堆有 \(A_i\) 个石子。每次可以选一堆从中取 \(\left[L, R\right]\) 个，问判断先手后手胜负。

（\(1 \le N \le 2 \times 10^5, 1 \le L \le R \le 10^9, 1 \le A_i \le 10^9\)）。

题解

考虑子游戏，即只有一堆石子的情况，考虑其 \(\operatorname{SG}\) 函数，首先给出结论

\[\operatorname{SG}(X) = \left\lfloor\dfrac{X \bmod \left(L + R\right)}{L}\right\rfloor \]

下面给出证明

若 \(0 \le X < L + R\)

• 如果 \(0 \le X < L\)，那么显然先手必输，此时 \(\operatorname{SG}(X) = 0\)；
• 如果 \(L \le X < 2 \cdot L\)，那么 \(X < L + R \Rightarrow X - R < L\)，所以此状态可以一步转移到所有 \(Y \in \left[X - R, X - L\right)\) 的状态，包含的 \(\operatorname{SG}\) 函数值集合为 \(\left\{0\right\}\)，此时 \(\operatorname{SG}(X) = 1\)；
• 如果 \(2 \cdot L \le X < 3 \cdot L\)，那么 \(X < L + R \Rightarrow X - R < L\)，所以此状态可以一步转移到所有 \(Y \in \left[X - R, X - L\right)\) 的状态，包含的 \(\operatorname{SG}\) 函数值集合为 \(\left\{0, 1\right\}\)，此时 \(\operatorname{SG}(X) = 2\)；
• 如果 \(3 \cdot L \le X < 4 \cdot L\)，那么 \(X < L + R \Rightarrow X - R < L\)，所以此状态可以一步转移到所有 \(Y \in \left[X - R, X - L\right)\) 的状态，包含的 \(\operatorname{SG}\) 函数值集合为 \(\left\{0, 1, 2\right\}\)，此时 \(\operatorname{SG}(X) = 3\)。

以此类推，可得 \(\operatorname{SG}(X) = \left\lfloor\dfrac{X}{L}\right\rfloor\)。

若 \(L + R \le X < 2 \cdot \left(L + R\right)\)

• 如果 \(L + R \le X < L + R + L\)，那么 \(L + R \le X \Rightarrow X - R \ge L\)，考虑到 \(\operatorname{SG}(L) = 1\)，所以此状态无法一步转移到 \(\operatorname{SG} = 0\) 的情况，因此此状态 \(\operatorname{SG}(X) = 0\)；
• 如果 \(L + R + L \le X < L + R + 2 \cdot L\)，那么 \(L + R + L \le X \Rightarrow X - R \ge 2 \cdot L\)，所以该状态可以一步转移到的 \(\operatorname{SG}\) 函数值集合为 \(\left\{0, 2, 3, 4, 5, \cdots, \left\lfloor\dfrac{L + R}{L}\right\rfloor\right\}\)，所以此状态 \(\operatorname{SG}(X) = 1\)。

同样的，对于所有 \(L + R \le X < 2 \cdot \left(L + R\right)\)，有 \(\operatorname{SG}(X) = \left\lfloor\dfrac{X \bmod \left(L + R\right)}{L}\right\rfloor\)。

若 \(2 \cdot \left(L + R\right) \le X\)

\(\operatorname{SG}(X)\) 的值仅会从 \(\operatorname{SG}(X - R), \operatorname{SG}(X - R + 1), \cdots, \operatorname{SG}(X - L)\) 中转移，类似于第二种情况，我们可以得出

\[\operatorname{SG}(X) = \left\lfloor\dfrac{X \bmod \left(L + R\right)}{L}\right\rfloor \]

Code

//AtCode - ABC297 - G
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;

int main() {
    valueType N, L, R;

    std::cin >> N >> L >> R;

    valueType SG = 0;

    for (valueType i = 0; i < N; ++i) {
        valueType A;

        std::cin >> A;

        SG ^= (A % (L + R)) / L;
    }

    if (SG > 0)
        std::cout << "First" << std::endl;
    else
        std::cout << "Second" << std::endl;

    return 0;
}

标签：right,cdot,题解,ABC297G,le,Constrained,SG,operatorname,left
From： https://www.cnblogs.com/User-Unauthorized/p/solution-AT-ABC297-G.html