假设 $l = 1$。
先放入一个特殊点 $P$,求出 $P$ 满足被至少 $k$ 条线段穿过的概率即为所求。
发现我们并不关心这 $2n+1$ 个点的绝对位置,而是需要关心这些点的前后顺序,由于每一个线段的选择都是从 $[1,0)$ 中随机选两个点,所以每 $2n+1$ 个点组成的序列,被选到的概率都是一样的,故根本不需要 $2n+1$ 个点的绝对位置。
设 $f_{i,j,t}$ 表示前 $i$ 个端点中,有 $j$ 个左端点未匹配到右端点,$P$ 是否已经出现的匹配方案数。
于是有三种转移 $f_{i,j,t}\to f_{i+1,j+1,t}$,$f_{i,j,t}\times j\to f_{i+1,j-1,t}$,$f_{i,j,0}\to f_{i,j,1}(j\ge k)$。
最终答案为 $ans=\frac{f_{2n,0,1}\times 2^n \times n!}{(2n+1)!}\times l$。
代码
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int, int>
using namespace std;
const int mod = 998244353;
int f[10010][5010][2];
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return res;
}
void add(int &x, int y) {
x += y;
if (x >= mod) x -= mod;
}
int main() {
int n, k, l;
scanf("%d%d%d", &n, &k, &l);
f[0][0][0] = 1;
for (int i = 0; i <= 2 * n; i ++ ) {
for (int j = 0; j <= i; j ++ ) {
if (j >= k) add(f[i][j][1], f[i][j][0]);
for (int y = 0; y < 2; y ++ ) {
if (j > 0) add(f[i + 1][j - 1][y], 1ll * f[i][j][y] * j % mod);
add(f[i + 1][j + 1][y], f[i][j][y]);
}
}
}
int fac = 1, fac2 = 1;
for (int i = 1; i <= n; i ++ ) fac = 1ll * fac * i % mod;
for (int i = 1; i <= 2 * n + 1; i ++ ) fac2 = 1ll * fac2 * i % mod;
printf("%d\n", 1ll * f[2 * n][0][1] * fac % mod * qpow(2, n) % mod * qpow(fac2, mod - 2) % mod * l % mod);
return 0;
}