题目链接：Codeforces 1153F

你有一条长度为 $l$ 的线段，我们通过随机选择 $2$ 点，在这条线端上随机选择 $n$ 条线段。这 $2n$ 个点将线段分成了 $2n + 1$ 个区间。你需要对于给定的 $k$，求出被这 $n$ 个随机线段中至少 $k$ 个覆盖的区间的期望总长度。答案对 $998244353$ 取模。

数据范围：$1 \le k \le n \le 2000$，$1 \le l \le 10 ^ 9$。

Solution

既然每个点的位置是实数，那么线段长度为 $l$ 和 $1$ 对答案没有影响，我们只需要把答案乘上 $l​$ 即可。

现在线段长度转化为了 $1$，那么合法区间期望总长度等价于：随机一个点 $P$ 使得这个点落在合法区间内的概率。

考虑一种特殊情况：随机的线段长度为 $0$，这种情况是否会发生呢？由于我们是通过随机两个点得到的随机线段，因此长度为 $0$ 的概率为 $0$，于是不需要考虑这种情况。

这样一来，我们就可以 $\text{DP}$ 了。考虑一共有 $2n + 1$ 个点，其中 $2n$ 个点为线段端点，另外一个点为随机的 $P$ 点。我们定义状态 $f(i, j, 0 / 1)$ 表示当前考虑到第 $i$ 个点，有 $j$ 个左端点没有匹配，是否已经选定了 $P$ 点，此时 $P$ 点落在合法区间的方案数。有如下转移：

• 当前点为左端点：$f(i, j, p) \leftarrow f(i - 1, j - 1, p)$。
• 当前点为右端点：$f(i, j, p) \leftarrow f(i - 1, j + 1, p) \times (j + 1)$。
• 当前点为 $P​$ 点：$f(i, j, 1) \leftarrow f(i - 1, j, 0)​$，其中必须保证 $j \ge k​$。

由于我们要求的是概率，因此要把方案数转为概率。总方案数为 $(2n + 1)!$ 种；这 $n$ 条线段的顺序可以互换，方案数为 $n!$ 种；每条线段的左右端点可以互换，方案数为 $2 ^ n$ 种。故概率为：

$$ \frac{f(2n + 1, 0, 1) \cdot l \cdot n! \cdot 2 ^ n}{(2n + 1)!} $$

时间复杂度：$\mathcal O(n ^ 2)$。

Code

#include <cstdio>
#include <cstring>

const int N = 2e3 + 5;
const int P = 998244353;

int n, m, l, f[N << 1][N][2];

void add(int &x, int y) {
    (x += y) >= P && (x -= P);
}
int fact(int n) {
    int ans = 1;
    for (int i = 1; i <= n; i++) ans = 1LL * ans * i % P;
    return ans;
}
int pow(int x, int p) {
    int ans = 1;
    for (; p; p >>= 1, x = 1LL * x * x % P) {
        if (p & 1) ans = 1LL * ans * x % P;
    }
    return ans;
}
int inv(int x) {
    return pow(x, P - 2);
}
int main() {
    scanf("%d%d%d", &n, &m, &l);
    int p = n << 1 | 1;
    f[0][0][0] = 1;
    for (int i = 1; i <= p; i++) {
        for (int j = 0; j <= n && j <= i; j++) {
            for (int k = 0; k <= 1; k++) {
                if (j > 0) add(f[i][j][k], f[i - 1][j - 1][k]);
                if (j < n) add(f[i][j][k], 1LL * f[i - 1][j + 1][k] * (j + 1) % P);
            }
            if (j >= m) add(f[i][j][1], f[i - 1][j][0]);
        }
    }
    int ans = 1LL * f[p][0][1] * l % P * fact(n) % P * pow(2, n) % P * inv(fact(p)) % P;
    printf("%d\n", ans);
    return 0;
}