@description@
从一条长度为 l 的线段中随机选择 n 条线段，共 2*n 个线段端点将这个线段分成 2*n + 1 个区间。
求这 2*n + 1 个区间中，被随机选择的 n 条线段中的至少 k 条覆盖的，区间的期望长度和。
对 998244353 取模。
Input
第一行三个整数 n, k 与 l (1≤k≤n≤2000, 1≤l≤10^9).
Output
输出一个整数，期望长度和对 998244353 取模的结果。
Examples
Input
1 1 1
Output
332748118
@solution@
首先有一个结论：如果随机将长度为 l 的线段划分成 k 个区间，则每个区间的期望长度为 l/k。（我也不会证）
这样连续期望就可以转为离散期望：
将 2*n 个点分配成 n 个线段，被至少 k 条线段覆盖的段的期望数量。
这样就可以做 dp 了：
定义 g[i][j] 表示前 i 个点已经分配完毕，其中还有 j 个左端点未匹配右端点，的方案数。
g[i][j] 的转移有两类：第 i 个点是左端点；第 i 个点是右端点，此时 j 个左端点都可以作为它的左端点，方案数乘 j。
定义 f[i][j] 表示前 i 个点已经分配完毕，其中还有 j 个左端点未匹配右端点，的被至少 k 条线段覆盖的总数量。
f[i][j] 的转移对应 g[i][j] 的转移也有两类，同时还要讨论 j >= k（i-1 ~ i 这一段是否被至少 k 条线段覆盖）与 j < k。
最后将 f[2n][0] 除以 g[2n][0]，就得到了离散期望 E。
将 E 乘 l/(2*n + 1) 即可得到答案。
@accepted code@
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN = 4000;
const int MOD = 998244353;
int pow_mod(int b, int p) {
int ret = 1;
while( p ) {
if( p & 1 ) ret = 1LL*ret*b%MOD;
b = 1LL*b*b%MOD;
p >>= 1;
}
return ret;
}
int f[MAXN + 5][MAXN + 5], g[MAXN + 5][MAXN + 5];
int main() {
int n, k, l;
scanf("%d%d%d", &n, &k, &l);
l = 1LL*l*pow_mod(2*n + 1, MOD-2)%MOD;
g[0][0] = 1;
for(int i=1;i<=2*n;i++) {
for(int j=0;j<i;j++)
g[i][j+1] = (g[i][j+1] + g[i-1][j])%MOD;
for(int j=1;j<=i;j++)
g[i][j-1] = (g[i][j-1] + 1LL*j*g[i-1][j]%MOD)%MOD;
}
for(int i=1;i<=2*n;i++) {
for(int j=1;j<=i;j++)
f[i][j-1] = 1LL*j*((f[i-1][j] + 1LL*(j >= k)*g[i-1][j]%MOD)%MOD)%MOD;
for(int j=0;j<i;j++)
f[i][j+1] = ((f[i][j+1] + f[i-1][j])%MOD + 1LL*(j >= k)*g[i-1][j]%MOD)%MOD;
}
cout << 1LL*f[2*n][0]*l%MOD*pow_mod(g[2*n][0], MOD-2)%MOD << endl;
}
@details@
没什么重要的细节吧。。。