题解 | #B

题目

输入

输出

思路

因为有t个连线露在外面，那么就意味着有t+1组球。

因为对于线来说，左兰州和右篮子是相同的，所以我们可以想象有无限个篮子，那么要有t个线，就应该t+1个篮子有球（球的个数不一定）。

如果t+1是奇数，那么就意味着一篮子有（t+1）/2+1个组，另一个篮子有（t+1）/2个组。

t+1如果是偶数，则左右都有（t+1）/2个组。

题目给出左篮子的球数x，要分成（t+1）/2+1组就用到了隔板法，就是x-1个位置选（t+1）/2+1-1个。

然后由于左篮子也可能有（t+1）/2个，所以有两种排列组合。

为了方便计组合数，可以将每个数的阶乘和逆元提前算出来。

完整代码

```#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int MAXN=1e6+5;
typedef long long ll;
ll ans=0;
ll ksm(ll base,ll mi){
    ll res=1;
    while(mi){
        if(mi & 1) res=res*base%mod;
        base=base*base%mod;
        mi >>=1 ;
    }
    return res;
}

ll inv(ll x){
    return ksm(x,mod-2);
}

ll fact[MAXN];
ll infact[MAXN];
void init(){
    fact[0]=1;
    for(ll i=1;i<MAXN;i++){
        fact[i]=fact[i-1]*i%mod;       
    }
    infact[MAXN-1]=inv(fact[MAXN-1]);
    for(int i=MAXN-2;i>=0;i--){
        infact[i]=infact[i+1]*(i+1)%mod;  
    }
}
ll c(ll a,ll b){
     if (a < 0 || b < 0 || b > a) return 0;
    return fact[a]*infact[b]%mod*infact[a-b]%mod;
}
signed main(){
    int t;
    cin>>t;
    init();
    
    while(t--){
        int n,x,t;
        cin>>n>>x>>t;
        if (t==0) {
            cout << (x == n ? 1 : 0) << '\n';
            continue;
        }
        int a,b;
        if((t+1)%2==1){
            a=(t+1)/2+1;
            b=(t+1)/2;
        }
        else{
            a=(t+1)/2;
            b=(t+1)/2;
        }
        ans=(c(n-x-1,a-1)*c(x-1,b-1)%mod+c(n-x-1,b-1)*c(x-1,a-1)%mod)%mod;
        cout<<ans<<"\n";
    }
    return 0;
}
//记得讨论t=0d的情况