CodeTON Round 8 E. Farm Game

看到这道题，我们首先应该猜猜结论，何时先手必胜，何时先手必败呢？

不妨假设 $a_i < b_i$：

对于 $a_1 < b_1 < a_2 < b_2$，我们能感觉到，$a_i$只会向右移动，因为假如 $a_i$ 左移，那么相应的 $b_i$ 也可以跟着左移，没有改善当前情况。

同理 $b_i$ 只会向左移动。

此时我们只关注 $g_i = b_i - a_i - 1$，相当于一个有 $n$ 堆石子的取石子游戏，每次选取若干堆每堆取走一个石子。

结论是如果所有堆都是偶数，那么先手必败。否则先手必胜。

首先全为 $0$ 为先手必败态，那么如果当前全为偶数，先手取完若干堆后，后手取和先手同样的，先手面临的局面还是全是偶数，这种情况下全为 $0$ 态显然先手会遇到。

如果当前不全是偶数，先手可以从所有奇数堆中取走一个，后手面临全是偶数的状态。

现在问题转化求所有堆都是偶数的方案数。

我们先枚举所有堆的个数之和，然后利用隔板法就可以求出将这些总数分配给 $n$ 堆的方案数。

比如当前总数是 $s$ ，那么分配的方案数就是 $C_{s/2+n-1}^{n-1}$。

分配完 $n$ 堆之后，我们将每堆都看成一个隔板，剩下数的个数为 $l-2n-s$，我们要将 $n$ 个隔板插入其中，让剩下的数分成 $n+1$堆，每堆个数可以为 $0$，方案数为 $C_{l-2n-s+n}^{n}$。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e6 + 10;
const int mod = 998244353;

int fac[N], invfac[N];

int qmi(int a, int b = mod - 2) {
    int res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int C(int a, int b) {
    if (a < 0 || b < 0 || a < b) {
        return 0;
    }
    return fac[a] * invfac[b] % mod * invfac[a - b] % mod;
}

void solve() {
    int l, n;
    cin >> l >> n;

    int ans = 0;
    for (int s = 0; s <= l; s += 2) {
        ans += C(s / 2 + n - 1, n - 1) * C(l - n - s, n) % mod;
        ans %= mod;
    }

    cout << 2 * (C(l, 2 * n) - ans + mod) % mod << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    fac[0] = 1;
    for (int i = 1; i < N; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    invfac[N - 1] = qmi(fac[N - 1]);
    for (int i = N - 2; i >= 0; i--) {
        invfac[i] = invfac[i + 1] * (i + 1) % mod;
    }

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}