Card Game题解

incra · 2023-06-23 10:35:29 · 个人记录

题目链接

题解

本文内容大部分翻译于官方题解。

考虑 DP。

可以证明，只有一种平局的情况。

证明：

如果 A 拿到了第 n 张卡片，那么他可以赢，所以第 n 张卡片只有 B 拿到了才有可能平局。

如果 B 拿到了第 n-1 张卡片，那么他可以赢因为 B 也同时拿了第 n 张卡片，所以第 n-1 张卡片被 A 拿走了。

如果 B 拿到了第 n-2 张卡片，那么他可以赢，有一种能使 B 赢得方法如下：

A 出 n-1，B 出 n，B 再出 n-2 就能赢了。

以此类推，每一张卡片都只能由一个固定的人拿走才能平局。

所以每一张卡片拿的人从 1 到 n 排序为 BAABBAAB...。

接下来考虑 DP。

设 f_{i,j,k} 表示 A 拿了 i 张卡片，B 拿了 j 张卡片，k=0/1/2，分别表示 A 赢了、B 赢了、平局的情况。

对应到平局时每一张卡片拿的人的状态，若拿当前的人与状态串相符的话，什么情况都能直接继承，否则的话，如果前一次是平局，那么这次的胜者就会是当前取走卡片的人。

不难推出，答案就是 f_{\frac{n}{2},\frac{n}{2},0/1/2}。

代码

#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 70,MOD = 998244353;
int n;
LL f[N][N][3];
int main () {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        memset (f,0,sizeof (f));
        f[0][0][2] = 1;
        int k = n / 2;
        for (int i = 0;i <= k;i++) {
            for (int j = 0;j <= k;j++) {
                for (int t = 0;t <= 2;t++) {
                    int turn = (i + j) % 4;
                    if (turn == 0 || turn == 3) {
                        if (i + 1 <= k) f[i + 1][j][t == 2 ? 0 : t] += f[i][j][t];
                        if (j + 1 <= k) f[i][j + 1][t] += f[i][j][t];
                    }
                    else {
                        if (i + 1 <= k) f[i + 1][j][t] += f[i][j][t];
                        if (j + 1 <= k) f[i][j + 1][t == 2 ? 1 : t] += f[i][j][t];
                    }
                }
            }
        }
        for (int i = 0;i <= 2;i++) cout << f[k][k][i] % MOD << ' ';
        cout << endl;
    }
    return 0;
}