← 返回题目列表

Codeforces · 1153/F

F. 仆人和奖金问题

中文机器翻译题面 查看原题

离数学家越来越近的薮猫成为了加帕里大学数学专业的大学生。在微积分课上,他的老师教他如何计算给定线段的随机子线段的预期长度。然后他留下了一道额外问题作为家庭作业,并获得了 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$$$)。

输出

输出一个整数 - $$$n$$$ 随机段中至少 $$$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}$$$。

示例

输入 #1

1 1 1

输出 #1

332748118

输入 #2

6 2 1

输出 #2

760234711

输入 #3

7 5 3

输出 #3

223383352

输入#4

97 31 9984524

输出#4

267137618

注意

在第一个示例中,预期总长度为 $$$\int_0^1 \int_0^1 |x-y| \,\mathrm{d}x\,\mathrm{d}y = {1\over 3}$$$,$$$3^{-1}$$$ 模 $$$998244353$$$ 为 $$$332748118$$$。