Gym 101147 A-The game of Osho

spirit

2021 年 05 月 13 日

1685 次浏览

暂无评论

1971字数

VJ训练赛博弈

# Gym 101147 A-The game of Osho

[题目链接](https://codeforces.com/gym/101147/problem/A) [参考博客](https://blog.csdn.net/V5ZSQ/article/details/64470793)

## Description

定义一个游戏：给定两个数字 $N$ 和 $B$ ，两个玩家轮流从 $N$ 中减去一个数字，减去的数值必须为一个整数 $B^k, k \geq 0$ ，减到 $0$ 为止，无法操作的玩家输掉游戏。该游戏的升级版本是：给出多个这样的游戏，两名玩家轮流选择一个游戏进行一步操作，无法操作的玩家输掉游戏。给出每一组 $N_i$ 和 $B_i$ ，确定哪位玩家赢得了游戏。

## Input

$T$ 组，每行先给出共有 $n$ 个子游戏，然后依次给出每对 $N_i$ 和 $B_i$ ，$1 \leq n \leq 100$ ，$1 \leq N_i, B_i \leq 1e9$ 。

```
3
1 2 3
1 7 3
2 6 11 3 2
```

## Output

输出 $1$ 代表先手获胜，$2$ 代表后手获胜。

```
2
1
2
```

## Solution

我们先来考虑子游戏的博弈情况：

- 如果 $B$ 为奇数：则 $B^k$ 一定为奇数，此时如果 $N$ 为奇数则先手必赢，否则后手必赢。
- 如果 $B$ 为偶数：则 $B^k = (B + 1 - 1)^k = X(B + 1) + (-1)^k$ ，当 $k$ 为偶数时 $B^k = X_1(B + 1) + 1$ ，否则 $B^k = X_2(B + 1) + B$ 。我们可以使 $N = Y(B + 1) + T, 0 \leq T \leq B$ ，此时问题可以转换为数字 $T$ ，每次可以减去 $1$ 或者 $B$ ，无法操作者输的游戏。这里之所以可以忽视前面若干个 $B + 1$ 的影响，是因为当 $T$ 和 $B$ 对于某一方为必赢态时，如果另一方试图通过拆解前面的一个 $B + 1$ 来影响游戏，他只能将其变为 $1$ 或 $B$ ，则必赢方可以立即消除该影响，对手依然是必输态。
  
  然后我们讨论 $T$ 和 $B$ 对游戏的影响，由 $T$ 的取值范围可知，只有当 $T = B$ 时，可以直接减去 $B$ ，否则只能轮流减去 $1$ ，此时只需要根据 $T$ 的奇偶就可以判断输赢。

但是解决多个子问题的合并需要使用 $SG$ 函数，接下来考虑 $SG$ 函数的取值情况：

- 如果 $B$ 为奇数：由于输赢态与奇偶有关，每一个必赢态（奇数）的后续状态一定都是必输态（偶数，$SG = 0$），所以对于每一个必赢态都有 $SG = 1$ 。
- 如果 $B$ 为偶数：当 $T < B$ 时，与前一种情况同理；当 $T = B$ 时，后续状态有 $T = B - 1, SG = 1$ 和 $T = 0, SG = 0$ 两种，所以此时 $SG = 2$ 。

最后对所有子游戏的 $SG$ 值求异或和即可。

## Code

```cpp
#include <bits/stdc++.h>

using namespace std;

int main() {
    freopen("powers.in", "r", stdin);
    int sg, flag, t, n, a, b;
    cin >> t;
    while (t--) {
        scanf("%d", &n);
        flag = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &b, &a);
            if (b & 1) {
                sg = a & 1;
            } else {
                int T = a % (b + 1);
                if (T == b) sg = 2;
                else sg = T & 1;
            }
            flag ^= sg;
        }
        puts(flag ? "1" : "2");
    }
    return 0;
}
```

最后修改：2021 年 05 月 13 日