一、题目意思

小 L 有 n 个编号 1 到 n 的彩球，分成左右两个盒子放，左边有 x 个，右边有 n-x 个。相邻编号的彩球如果在不同盒子，它们之间的连线就会露出来。现在已知有 t 条线露在外面，问符合条件的放法有多少种？答案对 998244353 取模。

二、个人理解

1. t 条线露在外面 → 所有球被分成 t+1 段连续小组，且小组在左右盒子交替放置； 2.左边 x 个球、右边 n−x 个球，要按 t 的奇偶性分配 “段数”；
2. 把 k 个球分成 s 段的方案数，用组合数 C (k−1, s−1) 计算（隔板法）；
3. 按 t 奇偶算左右需分的段数，将合法情况的组合数相乘 / 相加得到答案；
4. 预处理阶乘和逆元，快速计算组合数（避免超时）。

三、代码

#include <functional>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
#define endl '\n'
const int N = 1000005;
const int MAX = 998244353;

// fc[i] = i! ，im[i] = (i!)的逆元
ll fc[N], im[N];

// 快速幂
ll fun2(ll a, ll b) {
	ll t = 1;
	while (b) {
		if (b & 1) t = t * a % MAX;
		a = a * a % MAX;
		b >>= 1;
	}
	return t;
}

// 阶乘阶乘逆元
void fun1() {
	fc[0] = 1;
	// 阶乘
	for (int i = 1; i < N; i++) {
		fc[i] = fc[i - 1] * i % MAX;
	}
	// 先算最大阶乘的逆元，再倒推
	im[N - 1] = fun2(fc[N - 1], MAX - 2);
	for (int i = N - 2; i >= 0; i--) {
		im[i] = im[i + 1] * (i + 1) % MAX;
	}
}

// 计算组合数 C(n, k)
ll C(ll n, ll k) {
	// 不合法情况
	if (n < k || n < 0 || k < 0) return 0;
	// 组合数
	return fc[n] * im[k] % MAX * im[n - k] % MAX;
}

int main() {
	IOS;
	fun1(); // 预处理阶乘和逆元
	int T;
	cin >> T;
	while (T--) {
		int n, x, t;
		cin >> n >> x >> t;
		// 特殊情况：t=0 表示无线露出
		if (t == 0) {
			cout << (x == n || x == 0 ? 1 : 0) << endl;
			return 0;
		}
		ll ans = 0;
		int m = t + 1; // 总段数 
		// 情况1：总段数偶数（t奇数） 左右段数相等
		if (m % 2 == 0) {
			int a = m / 2; // 左右各分a段
			if (x >= a && (n - x) >= a) {
				// 乘2：可以先左后右，也可以先右后左
				ans = 2 * C(x - 1, a - 1) % MAX * C(n - x - 1, a - 1) % MAX;
			}
		} 
		// 情况2：总段数奇数（t偶数）左右段数相差1
		else {
			// 左多1段，右少1段
			int a1 = (m + 1) / 2, b1 = (m - 1) / 2;
			if (x >= a1 && (n - x) >= b1) {
				ans = (ans + C(x - 1, a1 - 1) * C(n - x - 1, b1 - 1)) % MAX;
			}
			// 右多1段，左少1段
			int a2 = (m - 1) / 2, b2 = (m + 1) / 2;
			if (x >= a2 && (n - x) >= b2) {
				ans = (ans + C(x - 1, a2 - 1) * C(n - x - 1, b2 - 1)) % MAX;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

四、验证

第一组：
n=3, x=1, t=2
t=2 → m=3（奇数）
a1=2, b1=1；a2=1, b2=2
检查 a1：x=1 < 2 → 不合法
检查 a2：x=1 ≥1，n-x=2 ≥2 → C (0,0)C(1,1)=11=1

第二组：
n=3, x=2, t=1
t=1 → m=2（偶数）
a=1 → 左右各 1 组
x=2≥1，n-x=1≥1 → 2C(1,0)C(0,0)=211=2

第三组：
n=4, x=2, t=2
t=2 → m=3（奇数）
a1=2, b1=1：x=2≥2，n-x=2≥1 → C(1,1)C(1,0)=11=1
a2=1, b2=2：x=2≥1，n-x=2≥2 → C(1,0)C(1,1)=11=1
总和 = 1+1=2