# CF1153F Serval and Bonus Problem

• 52通过
• 67提交
• 题目来源
• 评测方式 RemoteJudge
• 标签
• 难度 NOI/NOI+/CTSC
• 时空限制 1000ms / 256MB
• 提示：收藏到任务计划后，可在首页查看。

## 题意翻译

有一段长为$l$的线段，有$n$个区间，左右端点在$[0,l)$间均匀随机（可能不是整数）

求期望被至少$k$段区间覆盖的长度，对998244353取膜

## 题目描述

Getting closer and closer to a mathematician, Serval becomes a university student on math major in Japari University. On the Calculus class, his teacher taught him how to calculate the expected length of a random subsegment of a given segment. Then he left a bonus problem as homework, with the award of a garage kit from IOI. The bonus is to extend this problem to the general case as follows.

You are given a segment with length $l$ . We randomly choose $n$ segments by choosing two points (maybe with non-integer coordinates) from the given segment equiprobably and the interval between the two points forms a segment. You are given the number of random segments $n$ , and another integer $k$ . The $2n$ endpoints of the chosen segments split the segment into $(2n+1)$ intervals. Your task is to calculate the expected total length of those intervals that are covered by at least $k$ segments of the $n$ random segments.

You should find the answer modulo $998244353$ .

## 输入输出格式

输入格式：

First line contains three space-separated positive integers $n$ , $k$ and $l$ ( $1\leq k \leq n \leq 2000$ , $1\leq l\leq 10^9$ ).

输出格式：

Output one integer — the expected total length of all the intervals covered by at least $k$ segments of the $n$ random segments modulo $998244353$ .

Formally, let $M = 998244353$ . It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$ , where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$ . Output the integer equal to $p \cdot q^{-1} \bmod M$ . In other words, output such an integer $x$ that $0 \le x < M$ and $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


## 说明

In the first example, the expected total length is $\int_0^1 \int_0^1 |x-y| \,\mathrm{d}x\,\mathrm{d}y = {1\over 3}$ , and $3^{-1}$ modulo $998244353$ is $332748118$ .

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。