AT_abc275_e [ABC275E] Sugoroku 4

题目描述

高桥君正在玩双六游戏。

这个双六游戏有 $N+1$ 个格子，编号从 $0$ 到 $N$。高桥君从 $0$ 号格子出发，目标是到达 $N$ 号格子。

在这个双六游戏中，使用一个有 $M$ 种等概率结果的轮盘，结果分别为 $1$ 到 $M$。高桥君每次旋转轮盘，根据结果前进相应的步数。如果前进后超过了 $N$ 号格子，则会从 $N$ 号格子反弹回来，超出的步数向回走。

例如，当 $N=4$ 且高桥君在 $3$ 号格子时，如果轮盘结果为 $4$，则会超出 $N$ 号格子 $3+4-4=3$ 格，因此需要从 $4$ 号格子向回走 $3$ 格，最终到达 $1$ 号格子。

当高桥君到达 $N$ 号格子时，游戏结束。

请计算高桥君在最多旋转轮盘 $K$ 次的情况下，能够到达终点的概率，并对 $998244353$ 取模输出。

概率 $\bmod\ 998244353$ 的定义：本题中要求的概率一定是有理数。并且，在本题的约束下，若将概率表示为最简分数 $\frac{y}{x}$，则 $x$ 不会被 $998244353$ 整除。

此时，存在唯一的整数 $z$，满足 $0 \leq z \leq 998244352$ 且 $xz \equiv y \pmod{998244353}$。请输出这个 $z$。

输入格式

输入为一行，包含三个整数：

$N$ $M$ $K$

输出格式

输出答案。

输入输出样例 #1

输入 #1

2 2 1

输出 #1

499122177

输入输出样例 #2

输入 #2

10 5 6

输出 #2

184124175

输入输出样例 #3

输入 #3

100 1 99

输出 #3

0

说明/提示

约束

• $M \leq N \leq 1000$
• $1 \leq M \leq 10$
• $1 \leq K \leq 1000$
• 输入均为整数

样例解释 1

仅当轮盘结果为 $2$ 时，才能在 $1$ 次轮盘内到达终点。因此概率为 $\frac{1}{2}$。此时，$2 \times 499122177 \equiv 1 \pmod{998244353}$，所以输出 $499122177$。

由 ChatGPT 4.1 翻译