Codeforces Round 551 (Div. 2)
F
Serval and Bonus Problem
Codeforces
2600
原题
← E→
翻译中…

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$.

翻译中…

Input

翻译中…

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

翻译中…

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 \lt M$ and $x \cdot q \equiv p \pmod{M}$.

翻译中…

Note

翻译中…

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$.

翻译中…

样例

Input #1
1 1 1
Output #1
332748118
InputCopy OutputCopy
Input #2
6 2 1
Output #2
760234711
InputCopy OutputCopy
Input #3
7 5 3
Output #3
223383352
InputCopy OutputCopy
Input #4
97 31 9984524
Output #4
267137618
InputCopy OutputCopy
题目信息
题号
1153F
时间限制
1 s
内存限制
256 MB
标签
组合数学
动态规划
数学
概率论

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。