← 返回题目列表

Codeforces · 1096/E

E. 最佳射手

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

Hasan 喜欢玩游戏,最近发现了一款名为 TopScore 的游戏。在这个类似足球的游戏中,有 $$$p$$$ 球员进行点球大战。获胜者是得分最多的人。如果出现平局,则以同等概率随机宣布得分最高的选手之一为获胜者。

他们刚刚结束了比赛,现在正在等待结果。但有一个小问题!评委们把分数纸弄丢了!幸运的是,他们在迷路之前计算了分数总和,并且对于一些玩家,他们还记得他们得分的下限。然而,有关界限的信息是私人的,因此哈桑只知道他的界限。

根据现有数据,他知道自己的分数至少为$$$r$$$,分数总和为$$$s$$$。

因此,游戏的最终状态可以用 $$$p$$$ 整数 $$$a_1, a_2, \dots, a_p$$$ ($$$0 \le a_i$$$) 序列的形式表示 - 玩家的得分。 Hasan 是玩家编号 $$$1$$$,因此 $$$a_1 \ge r$$$。还有$$$a_1 + a_2 + \dots + a_p = s$$$。如果存在某个位置 $$$i$$$ 使得 $$$a_i$$$ 的值在这些状态中不同,则两个状态被视为不同。

哈桑再次不知道确切的分数(他也不知道自己的确切分数)。因此他认为每个最终状态都有相同的可能性实现。

帮助哈桑求出他获胜的概率。

可以证明它的形式为$$$\frac{P}{Q}$$$,其中$$$P$$$和$$$Q$$$是非负整数,$$$Q \ne 0$$$, $$$P \le Q$$$。报告 $$$P \cdot Q^{-1} \pmod {998244353}$$$ 的值。

输入

唯一的一行包含三个整数 $$$p$$$、$$$s$$$ 和 $$$r$$$ ($$$1 \le p \le 100$$$, $$$0 \le r \le s \le 5000$$$) — 分别是玩家数量、所有玩家得分总和以及哈桑得分。

输出

打印一个整数——哈桑获胜的概率。

可以证明它的形式为$$$\frac{P}{Q}$$$,其中$$$P$$$和$$$Q$$$是非负整数,$$$Q \ne 0$$$, $$$P \le Q$$$。报告 $$$P \cdot Q^{-1} \pmod {998244353}$$$ 的值。

示例

输入 #1

2 6 3

输出 #1

124780545

输入 #2

5 20 11

输出 #2

1

输入 #3

10 30 10

输出 #3

85932500

注意

在第一个示例中,Hasan 可以进球 $$$3$$$、$$$4$$$、$$$5$$$ 或 $$$6$$$ 进球。如果他进球 $$$4$$$ 或更多,那么他的得分就严格高于他唯一的对手。如果他得分 $$$3$$$,那么他的对手也得分 $$$3$$$,哈桑赢得比赛的概率为 $$$\frac 1 2$$$。因此,总体而言他获胜的概率为 $$$\frac 7 8$$$。

在第二个示例中,即使哈桑的进球下限也意味着他的得分比任何对手都多。因此,所得概率为 $$$1$$$。