题意

一个长为 \(l\) 的线段，每次等概率选择线段上两个点，共选出 \(n\) 条线段，求至少被 \(k\) 条线段覆盖的长度期望。

数据范围

\(1 \le k \le n \le 2000, 1 \le l \le 10^9\)

题解

坑爹的 \(\text E\) 浪费了我好多时间，导致没时间做。。

由于每个端点出现的概率互相独立，我们可以只考虑端点的相对顺序。

那么每相邻的两个点把线段分成了 \(2n + 1\) 个段，显然每段的期望长度是 \(\displaystyle \frac{l}{2n + 1}\) 。

然后我们只需要 \(dp\) 出期望有多少段被 \(k\) 个线段覆盖。那么给这 \(2n\) 个断点匹配，算合法方案了。

只要设 \(f_{i, j}\) 为前 \(i\) 个端点，还有 \(j\) 个左端点没有匹配上右端点的方案数，然后每次转移的时候，要么填左端点，要么填右端点（每个右端点可以任意匹配一个左端点）。

最后对于每个段单独算一下合法的匹配方案数即可，不要忘记除掉 \(f_{n, 0}\) 才是期望。

总结

对于均匀实数随机的期望问题，如果是分别且独立，通常可以考虑每一段的期望，然后直接当做离散模型进行 \(dp\) 即可。

代码

#include 
    
     #define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)#define Set(a, v) memset(a, v, sizeof(a))#define Cpy(a, b) memcpy(a, b, sizeof(a))#define debug(x) cout << #x << ": " << (x) << endlusing namespace std;template
     
       inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }template
      
        inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }inline int read() {    int x(0), sgn(1); char ch(getchar());    for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;    for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);    return x * sgn;}void File() {#ifdef zjp_shadow    freopen ("F.in", "r", stdin);    freopen ("F.out", "w", stdout);#endif}const int Mod = 998244353;inline int fpm(int x, int power) {    int res = 1;    for (; power; power >>= 1, x = 1ll * x * x % Mod)        if (power & 1) res = 1ll * res * x % Mod;    return res;}const int N = 2e3 + 1e2;int f[N << 1][N], fac[N];int main () {    File();    int n = read(), k = read(), l = read();    f[0][0] = 1;    For (i, 0, n << 1) For (j, 0, min(n, i)) if (f[i][j]) {        (f[i + 1][j + 1] += f[i][j]) %= Mod;        if (j) f[i + 1][j - 1] = (f[i + 1][j - 1] + 1ll * f[i][j] * j) % Mod;    }    int ans = 0;    fac[0] = 1;    For (i, 1, n) fac[i] = 1ll * fac[i - 1] * i % Mod;    For (i, 1, n << 1) For (j, k, min(n, i))        ans = (ans + 1ll * f[i][j] * f[(n << 1) - i][j] % Mod * fac[j]) % Mod;    ans = 1ll * ans * l % Mod * fpm(2 * n + 1, Mod - 2) % Mod * fpm(f[n << 1][0], Mod - 2) % Mod;    printf ("%d\n", ans);    return 0;}