「Codeforces 1739C」Card Game - 组合数学 + 博弈论

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

Codeforces 链接

Alice 和 Bob 玩游戏，游戏中有 \(n\) 张标有 \(1 \sim n\) 数字卡牌（\(n\) 为偶数），开局时 Alice 和 Bob 均有 \(\frac{n}{2}\) 张。在每一轮中，其中一人先打出自己一张卡牌，然后另一人再打出自己的一张卡牌。若后手无法打出比前一人打出卡牌数字大的卡牌，则后手输；否则进入下一轮。该轮的后手为下一轮的先手。若卡牌打完则平局。在这个游戏中，Alice 为第一轮的先手。假设双方均按最优策略出牌，求 Alice 赢、Bob 赢和平局的情况数。答案对 \(998244353\) 取模。

解题思路

对于每一轮，我们显然可以得出：若先手有目前双方未打出的最大的牌，则先手打出这张牌必胜，否则后手可打出更大的牌结束该轮。于是我们只考虑最大的牌和次大的牌，分别分情况讨论：

  1. 先手拥有最大的牌，则先手必胜；
  2. 后手同时拥有最大的牌和次大的牌，则先手必输；
  3. 先手拥有次大的牌，后手拥有最大的牌，此时的最优策略是先手打掉次大的牌，后手打掉最大的牌，进入下一轮。

对于每一种情况，我们用组合数学求出即可。我们存储 Alice 和 Bob 赢的情况，将 \(n\) 从大到小两两一组讨论，假设最大牌为 \(i\)：

  1. 对于情况 \(1\)，先手获胜情况数加 \({i - 1 \choose \frac{n}{2} - 1 - \frac{n - i}{2}}\)，即先手的剩下的卡牌为在 \(i - 1\) 个数中选择的情况数；
  2. 对于情况 \(2\)，后手获胜情况数加 \({i - 2 \choose \frac{n}{2} - \frac{n - i}{2}}\)，即后手的剩下的卡牌在 \(i - 2\) 个数中选择的情况数。

每讨论完一组就换先手继续讨论。平局的情况数显然为 \(1\)，这样我们就可以得出获胜的情况数了。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#include <iostream>

const int MAXN = 60;
const int MOD = 998244353;

long long fac[MAXN + 1], inv[MAXN + 1], facInv[MAXN + 1];

inline int C(const int n, const int k) {
    if (k < 0 || k > n) return 0;
    if (k == 0) return 1;
    return fac[n] * facInv[k] % MOD * facInv[n - k] % MOD;
}

inline long long lucas(long long n, long long k) {
    if (!k) return 1;
    return C(n % MOD, k % MOD) * lucas(n / MOD, k / MOD) % MOD;
}

inline void prepare() {
    fac[0] = 1;
    for (int i = 1; i <= MAXN; i++) fac[i] = fac[i - 1] * i % MOD;

    inv[1] = 1;
    for (int i = 2; i <= MAXN; i++) inv[i] = ((-(MOD / i) * inv[MOD % i]) % MOD + MOD) % MOD;

    facInv[0] = 1;
    for (int i = 1; i <= MAXN; i++) facInv[i] = facInv[i - 1] * inv[i] % MOD;
}

void solve() {
    int n;

    scanf("%d", &n);

    long long ans1 = 0, ans2 = 0;
    bool flag = true;
    for (int i = n; i >= 1; i -= 2) {
        if (flag) {
            ans1 = (ans1 + lucas(i - 1, n / 2 - 1 - (n - i) / 2)) % MOD;
            ans2 = (ans2 + lucas(i - 2, n / 2 - (n - i) / 2)) % MOD;
        } else {
            ans2 = (ans2 + lucas(i - 1, n / 2 - 1 - (n - i) / 2)) % MOD;
            ans1 = (ans1 + lucas(i - 2, n / 2 - (n - i) / 2)) % MOD;
        }
        flag ^= true;
    }

    printf("%lld %lld 1\n", ans1, ans2);
}

int main() {
    prepare();

    int t;

    scanf("%d", &t);

    while (t--) solve();

    return 0;
}