将原线段缩成1， 因为线段长度不影响结果 2n个点将线段分成了2n+1条线段， 我们有理由认为这 2 n + 1 2n+1 2n+1条子线段的期望等长。 证明： 第一条线段大于等于x的概率 ( 1 − x ) 2 n (1-x)^{2n} (1−x)2n 对上式求导，得等于x的概率 2 n ( 1 − x ) 2 n − 1 2n(1-x)^{2n-1} 2n(1−x)2n−1 第一段的长度期望为 E 1 = 2 n ∫ 0 1 x ( 1 − x ) 2 n − 1 d x = 1 2 n + 1 E_{1}=2n\int^1_0 x(1-x)^{2n-1}dx=\frac{1}{2n+1} E1=2n∫01x(1−x)2n−1dx=2n+11 归纳一下，后面也必然相同
考虑dp, 自然想到dp[i][j]表示为第i个有j没匹配的方案数， 方案数考虑每条线段的顺序事先排好,然后前后匹配一下即可. 之前考虑用概率Wa了，因为每种转移往后的方案数不一定相等，及不是等概率的增删。
#include<bits/stdc++.h> using namespace std; const int MAX_N = 4e3 + 5; typedef long long ll; ll dp[MAX_N][MAX_N]; ll r[MAX_N], f[MAX_N]; const ll mod = 998244353; int n, k, l; void init() { r[1] = 1; f[0] = 1; for (int i = 2; i < MAX_N; i++) r[i] = r[mod%i] * (mod - mod / i) % mod; for (int i = 1; i <MAX_N; i++) f[i] = f[i - 1]*i % mod; } //错的原因： 取和用等概率的条件是剩下的各种情况数相同， 但显然不同。 ll val_select(int turn, int now) { int died = (turn - now) / 2, left = n - now - died; bool ans = (0 <= now && now <= n - 1) && (0 <= died && died <= n) && 1 <= left; return ans; } ll val_remove(int turn, int now) { int died = (turn - now) / 2, left = n - now - died; bool ans = (1 <= now && now <= n) && (0 <= died && died <= n) && 0 <= left; return ans*now; } ll mod_r(ll x) { ll res = 1, n = mod - 2; while (n) { if (n & 1) res = res * x%mod; x = x * x%mod; n >>= 1; } return res; } int main() { init(); cin >> n >> k>>l; dp[0][0] = 1; for (int i = 1; i <=2*n; i++) { for (int j = 0; j <= min(n, i); j++) { dp[i][j] += dp[i - 1][j - 1] * val_select(i - 1, j - 1) % mod; dp[i][j] += dp[i - 1][j + 1] * val_remove(i - 1, j + 1) % mod; } } ll ans = 0; for (int i = 1; i <= 2 * n; i++) { for (int j = k; j <= n; j++) { ans = (ans + dp[i][j] * dp[2 * n - i][j] % mod*f[j]) % mod; } } ans = ans * r[2 * n + 1] % mod*l%mod * mod_r(dp[2*n][0])%mod; cout << ans << endl; //system("pause"); }