AT_abc298_e [ABC298E] Unfair Sugoroku

题目描述

高桥君和青木君在玩双陆游戏。
高桥君起始在位置 $A$，青木君起始在位置 $B$，两人轮流掷骰子。
高桥君使用的骰子可以掷出 $1, 2, \ldots, P$，每个点数出现的概率相同；青木君使用的骰子可以掷出 $1, 2, \ldots, Q$，每个点数出现的概率相同。
当某人在位置 $x$ 时，若他掷出的点数为 $i$，则他会前进到位置 $\min(x + i, N)$。
最先到达位置 $N$ 的人获胜。
高桥君先手。请你求出高桥君获胜的概率，对 $998244353$ 取模。

关于概率 $\bmod 998244353$ 的说明：本题中要求的概率一定是有理数，并且在本题的约束条件下，若将概率表示为最简分数 $\frac{y}{x}$，则 $x$ 一定不会被 $998244353$ 整除。
此时，存在唯一的整数 $z$，满足 $0 \leq z \leq 998244352$ 且 $xz \equiv y \pmod{998244353}$。请输出这个 $z$。

输入格式

输入由标准输入给出，格式如下：

$N$ $A$ $B$ $P$ $Q$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4 2 3 3 2

输出 #1

665496236

输入输出样例 #2

输入 #2

6 4 2 1 1

输出 #2

1

输入输出样例 #3

输入 #3

100 1 1 10 10

输出 #3

264077814

说明/提示

约束条件

• $2 \leq N \leq 100$
• $1 \leq A, B < N$
• $1 \leq P, Q \leq 10$
• 输入均为整数

样例解释 1

高桥君在第一回合掷出 $2$ 或 $3$ 时，会到达位置 $4$ 并获胜。若掷出 $1$，则移动到位置 $3$，此时青木君下一回合必定到达位置 $4$ 并获胜。因此高桥君获胜的概率为 $\frac{2}{3}$。

样例解释 2

骰子的点数始终为 $1$。此时高桥君会移动到位置 $5$，接着青木君移动到位置 $3$，然后高桥君移动到位置 $6$，所以高桥君必胜。

由 ChatGPT 4.1 翻译