当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

7239:Matryoshka Doll

题目描述
<tt>zyb</tt> bought $n$ matryoshka dolls during his visit to Moscow, with sizes $a_1,a_2,\dots,a_n$, respectively, <strong>sorting from smallest to largest</strong>.

A matryoshka of size $i$ can be put into another matryoshka of size $j$ if and only if $j-i\geq r$, where $r$ is some given integer parameter.

<tt>zyb</tt> wishes to divide all $n$ matryoshka dolls into $k$ groups, such that one can form a <strong>nested</strong> matryoshka doll in each group, where a group of matryoshka dolls with indices $c_1,c_2,...,c_m$ ($1\leq c_1\lt c_2\lt ...\lt c_m \leq n$) can form a <strong>nested</strong> matryoshka doll iff $\forall 1\leq i\lt m, a_{c_i}+r\leq a_{c_{i+1}}$.

<tt>zyb</tt> wants to know how many ways there are to divide the $n$ dolls into $k$ groups satisfying the requirement above. Note that divisions such as $\{ \{ 1,2\} ,\{ 3,4\} \}$ and $\{ \{ 3,4\} ,\{ 1,2\} \}$ are considered the same way. As the answer may be too large, you only need to output the answer modulo $998244353$.
输入解释
The first line contains an integer $T(1\leq T\leq 20)$, denoting the number of test cases.

For each test case, the first line contains three integers $n,k,r(1\leq k\leq n\leq 5000, 1\leq r\leq 10^9)$, denoting the number of matryoshka dolls, the number of groups <tt>zyb</tt> wants to divide into, and the parameter, respectively.

The next line contains $n$ integers $a_1,a_2,\dots,a_n(1\leq a_1\leq a_2\leq ... \leq a_n\leq 10^9)$, denoting the sizes of the matryoshka dolls.

It is guaranteed that $\sum n\leq 50000$ over all test cases.
输出解释
For each test case, output an integer in a line, denoting the answer taken modulo $998244353$.
输入样例
2
4 3 2
1 2 3 4
4 2 1
1 1 2 2
输出样例
3
2

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-7239

最后修改于 2022-09-15T06:17:34+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
5000/2500MS(Java/Others) 524288/524288K(Java/Others)