← 返回题目列表

Codeforces · 1765/C

C. 猜牌

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

考虑一副牌。每张牌都有 $$$4$$$ 花色中的一张,并且每种花色正好有 $$$n$$$ 卡 — 因此,这副牌中的牌总数为 $$$4n$$$。这副牌是随机洗牌的,因此这副牌中每个可能的 $$$(4n)!$$$ 顺序的牌都有相同的洗牌结果概率。令 $$$c_i$$$ 为这副牌中的第 $$$i$$$ 张牌(从上到下)。

Monocarp 开始从牌堆中一张一张地抽牌。在抽牌之前,他会尝试猜测它的花色。 Monocarp 记得最后一张 $$$k$$$ 牌的花色,他的猜测是他抽到的最后 $$$k$$$ 牌中出现次数最少的花色。因此,在抽出第 $$$i$$$ 张牌时,Monocarp 猜测其花色是 $$$c_{i-k}, c_{i-k+1}, \dots, c_{i-1}$$$ 牌中出现次数最少的花色(如果 $$$i \le k$$$,Monocarp 会考虑之前抽出的所有牌,即 $$$c_1, c_2, \dots, c_{i-1}$$$)。如果 Monocarp 记住的之前的牌中有多个出现次数最少的花色,他会从这些花色中随机选择一个花色进行猜测(所有出现次数最少的花色被选择的概率相同)。

做出猜测后,Monocarp 抓一张牌并将其花色与他的猜测进行比较。如果匹配,那么他的猜测是正确的;如果匹配,那么他的猜测是正确的。否则它是不正确的。

你的任务是计算 Monocarp 从牌堆中抽出所有 $$$4n$$$ 卡后预计正确猜测的次数。

输入

第一行(也是唯一的一行)包含两个整数 $$$n$$$ ($$$1 \le n \le 500$$$) 和 $$$k$$$ ($$$1 \le k \le 4 \cdot n$$$)。

输出

令您必须计算的期望值为不可约分数 $$$\dfrac{x}{y}$$$。打印一个整数 - $$$x \cdot y^{-1} \bmod 998244353$$$ 的值,其中 $$$y^{-1}$$$ 是 $$$y$$$ 的倒数(即满足 $$$y \cdot y^{-1} \bmod 998244353 = 1$$$ 的整数)。

示例

输入 #1

1 1

输出 #1

748683266

输入 #2

3 2

输出 #2

567184295

输入 #3

2 7

输出 #3

373153250

输入#4

2 8

输出#4

373153250