题解 | #B Problem#

解题思路：

如果把n个球排成一排不动，我们只要考虑左右盒子放在哪里，用的是数学里面的隔板法

1 2 3 4 5 6 7 8 8

L L|R R R |L L L

|代表就是t，那么t为奇数时候，就会分成偶数块，如果是偶数时候，就会分成奇数块，那么我们将分类讨论是L的多一个还是R多一个，下面是代码（用到了组合数）

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl '\n'

const int mod = 998244353;
const int N = 1000005;

int fac[N], inv[N]; // 存放阶乘和阶乘的逆元
// 快速幂
int power(int a, int b)
{
    int res = 1;
    while (b > 0)
    {
        if (b % 2 == 1)
        {
            res = res * a % mod;
        }
        a = a * a % mod;
        b /= 2;
    }
    return res;
}
// 预处理：在程序刚开始的时候将所有的阶乘算好
void pre()
{
    fac[0] = 1;
    for (int i = 1; i < N; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    // 用费马小定理算逆元
    inv[N - 1] = power(fac[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
// 计算组合数
int ncr(int n, int k)
{
    if (k < 0 || k > n)
        return 0;
    return fac[n] * inv[k] % mod * inv[n - k] % mod;
}

void solve()
{
    int n, x, t;
    cin >> n >> x >> t;
    //特判： 如果球全在一个盒子里的
    if (x == 0 || x == n)
    {
        if (t == 0)
            cout << 1 << endl;
        else
            cout << 0 << endl;
        return;
    }
    //t是奇数的话，分为4块
    if (t % 2 == 1)
    {
        int m = (t + 1) / 2;//左右各有m块
        int ans = 2 * ncr(x - 1, m - 1) % mod * ncr(n - x - 1, m - 1) % mod;
        cout << ans << endl;
    }
    else
    {//块数为奇数
        int m = t / 2;
        //可能L比R多一块
        int sum1 = ncr(x - 1, m) * ncr(n - x - 1, m - 1) % mod;
        //可能R比L多一块
        int sum2 = ncr(n - x - 1, m) * ncr(x - 1, m - 1) % mod;
        cout << (sum1 + sum2) % mod << endl;
    }
}

signed main()
{
    ios;
    int T;
    pre();
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}