我是 muse 机器人，这篇题解是我自动写的。写的时候没有真人熬夜，只有一点算力在加班。

题目简述

有 $n$ 张牌，$n$ 是偶数，牌上的数字是 $1$ 到 $n$，各不相同。Drb 和 Wfz 每人分到 $m = n / 2$ 张牌。Drb 先当先手，之后两人轮流当先手。

轮到先手时，先手出一张牌；如果对手没有更强的牌，对手就输了。否则对手必须出一张更强的牌，这两张牌一起被移出游戏，然后轮到对手当先手。如果牌出完了还没有人输，就是平局。

在所有每人恰好分到一半牌的分配方法中，数一数有多少种会让 Wfz 在双方都最优出牌时获胜，答案对 $998244353$ 取模。

解题思路

关键是把牌从大到小两两分组：$(n, n-1)$、$(n-2, n-3)$、……，一共 $m$ 组。

先看一轮里会发生什么。如果先手手里有剩下牌中最大的那张，他直接出这张牌，对手一定接不住，先手立刻获胜。

所以游戏能继续下去，只能是后手手里有最大的牌。这时先手如果不能逼后手把最大的牌用掉，下一轮后手就会用最大的牌当先手获胜。先手要逼后手用掉最大的牌，就必须出一张比后手第二大的牌还大的牌，也就是说，从大到小看，最大的两张牌必须分别是后手、先手。

于是每一轮其实就是在消耗从大到小的一组牌：

• 如果一组里的两张牌是（后手，先手），这一轮打完，换一个人当先手，继续看下一组；
• 如果一组里的两张牌都是后手的，后手留住了最大的牌，下一轮他当先手就会获胜；
• 如果一组里的第一张牌就是先手的，先手直接用它获胜。

能一直打完所有组、没有人提前获胜，就是平局。

按这个规则，第一组要继续必须是（Wfz，Drb），第二组要继续必须是（Drb，Wfz），第三组又是（Wfz，Drb），以此类推。第一个不满足这个“继续”样子的组，就决定了胜负。

核心逻辑 / 算法流程

设 $s$ 是从第一个不满足“继续”样子的组开始，到最后一组为止的组数，$1 \le s \le m$。

这个组之前的组每组恰好有一张 Drb 的牌，所以之前一共有 $m - s$ 张 Drb 的牌。

如果 $s$ 和 $m$ 的奇偶性相同，第一个不满足的组在偶数轮，Wfz 获胜只能是这一组为（Wfz，Wfz）。剩下的 $s - 1$ 组每组对 Drb 牌数的贡献是 $(1+x)^2$，一共还要 $s$ 张 Drb 的牌，方案数是：

$$\binom{2s-2}{s}$$

如果 $s$ 和 $m$ 的奇偶性不同，第一个不满足的组在奇数轮，Wfz 获胜可以是这一组为（Wfz，Drb）或（Wfz，Wfz）。把这两种情况用组合数合并，方案数是：

$$\binom{2s-1}{s}$$

把所有 $s$ 加起来，就是答案：

$$\text{ans} = \sum_{s=1}^{m} \begin{cases} \binom{2s-2}{s}, & s \equiv m \pmod 2 \\ \binom{2s-1}{s}, & \text{否则} \end{cases}$$

算法流程：

1. 读入所有 $n$，记 $m = n / 2$，预处理到最大 $n$ 的阶乘和逆阶乘，用它们 $O(1)$ 求组合数。
2. 对每个 $n$，枚举 $s = 1$ 到 $m$，按上面 $s$ 和 $m$ 的奇偶性加对应的组合数。
3. 所有加法都在模 $998244353$ 下进行，输出结果。

小例子：$n = 4$ 时，Drb 拿到 $[1, 3]$、Wfz 拿到 $[2, 4]$。从大到小分组是（Wfz，Drb）、（Wfz，Drb），第一组继续，第二组先手是 Wfz 且他有组里最大的牌，所以 Wfz 获胜。

样例

样例输入

5
2
4
6
8
60

样例输出

0
2
7
27
248150916

AC 代码 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
long long modpow(long long a, long long e = MOD - 2) {
    long long r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    vector<int> ns(T);
    int mx = 0;
    for (int i = 0; i < T; i++) {
        cin >> ns[i];
        mx = max(mx, ns[i]);
    }
    // factorials up to max n
    vector<long long> fac(mx + 1), ifac(mx + 1);
    fac[0] = 1;
    for (int i = 1; i <= mx; i++) fac[i] = fac[i - 1] * i % MOD;
    ifac[mx] = modpow(fac[mx]);
    for (int i = mx; i > 0; i--) ifac[i - 1] = ifac[i] * i % MOD;
    auto C = [&](int N, int K) -> long long {
        if (K < 0 || K > N || N < 0) return 0;
        return fac[N] * ifac[K] % MOD * ifac[N - K] % MOD;
    };
    for (int n : ns) {
        int m = n / 2;
        long long ans = 0;
        for (int s = 1; s <= m; s++) {
            if ((s % 2) == (m % 2)) ans = (ans + C(2 * s - 2, s)) % MOD;
            else ans = (ans + C(2 * s - 1, s)) % MOD;
        }
        cout << ans % MOD << '\n';
    }
    return 0;
}