102754: [AtCoder]ABC275 E - Sugoroku 4
Description
Score : $500$ points
Problem Statement
Takahashi is playing sugoroku, a board game.
The board has $N+1$ squares, numbered $0$ to $N$. Takahashi starts at square $0$ and goes for square $N$.
The game uses a roulette wheel with $M$ numbers from $1$ to $M$ that appear with equal probability. Takahashi spins the wheel and moves by the number of squares indicated by the wheel. If this would send him beyond square $N$, he turns around at square $N$ and goes back by the excessive number of squares.
For instance, assume that $N=4$ and Takahashi is at square $3$. If the wheel shows $4$, the excessive number of squares beyond square $4$ is $3+4-4=3$. Thus, he goes back by three squares from square $4$ and arrives at square $1$.
When Takahashi arrives at square $N$, he wins and the game ends.
Find the probability, modulo $998244353$, that Takahashi wins when he may spin the wheel at most $K$ times.
How to print a probability modulo $998244353$
It can be proved that the sought probability is always a rational number. Additionally, under the Constraints of this problem, when the sought probability is represented as an irreducible fraction $\frac{y}{x}$, it is guaranteed that $x$ is not divisible by $998244353$.
Here, there is a unique integer $z$ between $0$ and $998244352$ such that $xz \equiv y \pmod{998244353}$. Print this $z$.
Constraints
- $M \leq N \leq 1000$
- $1 \leq M \leq 10$
- $1 \leq K \leq 1000$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $K$
Output
Print the answer.
Sample Input 1
2 2 1
Sample Output 1
499122177
Takahashi wins in one spin if the wheel shows $2$. Therefore, the probability of winning is $\frac{1}{2}$.
We have $2\times 499122177 \equiv 1 \pmod{998244353}$, so the answer to be printed is $499122177$.
Sample Input 2
10 5 6
Sample Output 2
184124175
Sample Input 3
100 1 99
Sample Output 3
0
Input
题意翻译
maze 在一个有 $N+1$ 个格子的棋盘上玩游戏，棋盘上的编号从 $0$ 到 $N$，初始在编号 $0$ 出有一枚棋子。 在一轮游戏中，maze 会随机选择 $1$ 到 $M$ 中的一个数$a$，并将棋子向 $N$ 处移动 $a$ 个格子。如果移动 $a$ 个格子会超过 $N$ ，则会在 $N$ 处掉头向 $0$ 移动剩下的步数。 举个例子：当 $N=4$， $a=4$ ，且 maze 当前在编号为 $3$ 的格子处，则到达 $N$ 时还有 $3$ 步没有走完，会向编号为 $1$ 的格子走 $3$ 步，最终到达编号为 $1$ 的格子处。 若一轮移动完后最终到达编号为 $N$ 的格子，那么游戏会立即结束。现在你需要求出在不多于 $k$ 轮游戏中结束游戏的概率，对 $998244353$ 取模。Output
得分：500分
问题描述
高桥正在玩一个棋盘游戏——双六。
棋盘上有$N+1$个格子，编号为$0$到$N$。 高桥从编号为$0$的格子出发，目标是编号为$N$的格子。
游戏使用一个有$M$个从$1$到$M$的数字的转盘，每个数字出现的概率相等。 高桥转动转盘，然后前进转盘显示的格子数。如果这会让他超出编号为$N$的格子，那么他在编号为$N$的格子处转身，返回超出的格子数。
例如，假设$N=4$，高桥在编号为$3$的格子上。如果转盘显示$4$，那么超出编号为$4$的格子的格子数为$3+4-4=3$。因此，他从编号为$4$的格子返回$3$个格子，到达编号为$1$的格子。
当高桥到达编号为$N$的格子时，他获胜，游戏结束。
求高桥最多可以转动转盘$K$次时，他获胜的概率（对$998244353$取模）。
如何对$998244353$取模打印概率
可以证明，所求概率始终为有理数。 此外，在本问题的约束条件下，当所求概率表示为不可约分数$\frac{y}{x}$时，可以保证$x$不被$998244353$整除。
这里存在一个唯一的整数$z$，在$0$和$998244352$之间，满足$xz \equiv y \pmod{998244353}$。打印这个$z$。
约束
- $M \leq N \leq 1000$
- $1 \leq M \leq 10$
- $1 \leq K \leq 1000$
- 输入中的所有值都是整数。
输入
输入从标准输入以如下格式给出：
$N$ $M$ $K$
输出
打印答案。
样例输入1
2 2 1
样例输出1
499122177
如果转盘显示$2$，高桥可以在一回合内获胜。因此，获胜概率为$\frac{1}{2}$。
我们有$2\times 499122177 \equiv 1 \pmod{998244353}$，所以需要打印的答案是$499122177$。
样例输入2
10 5 6
样例输出2
184124175
样例输入3
100 1 99
样例输出3
0