CF1153F Serval and Bonus Problem

越来越接近数学家的 Serval 成为了 Japari 大学数学专业的一名大学生。在微积分课上，老师教他如何计算给定线段的随机子线段的期望长度。然后老师留了一个加分题作为作业，奖励是一套 IOI 的手办。加分题是将这个问题推广到更一般的情形： 给定一条长度为 $l$ 的线段。我们随机选择 $n$ 条线段，每次通过在给定线段上等概率地选择两个点（坐标可以不是整数），这两个点之间的区间构成一条线段。你会得到随机选择的线段数 $n$ 和另一个整数 $k$。这 $2n$ 个端点将原线段分成了 $2n+1$ 个区间。你的任务是计算被 $n$ 条随机线段中至少 $k$ 条覆盖的所有区间的期望总长度。 你需要将答案对 $998244353$ 取模。

第一行包含三个用空格分隔的正整数 $n$、$k$ 和 $l$（$1\leq k \leq n \leq 2000$，$1\leq l\leq 10^9$）。

输出一个整数——所有被至少 $k$ 条线段覆盖的区间的期望总长度对 $998244353$ 取模的结果。 形式化地，设 $M = 998244353$。可以证明答案可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not \equiv 0 \pmod{M}$。输出等于 $p \cdot q^{-1} \bmod M$ 的整数。换句话说，输出一个整数 $x$，满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$。

在第一个样例中，期望总长度为 $\int_0^1 \int_0^1 |x-y| \,\mathrm{d}x\,\mathrm{d}y = \frac{1}{3}$，而 $3^{-1}$ 对 $998244353$ 取模的结果是 $332748118$。 由 ChatGPT 4.1 翻译