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

· · 题解

更好的阅读体验请点这

题意描述

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，这样我们就可以得出获胜的情况数了。

代码演示

#include <cstdio>
#include <iostream>

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

long long fac[MAXN + 1], inv[MAXN + 1], facInv[MAXN + 1], f[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;

    f[0] = 0, f[1] = 0, f[2] = 1;
    for (int i = 3; i <= MAXN; i++) {
        f[i] = (i - 1) * (f[i - 1] + f[i - 2]) % 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;
}