E - Dice Product 3
当前没有测试数据。
E - 骰子乘积 3
得分: $500$ 分
题目描述
你有一个整数 $1$ 和一个骰子，显示从 $1$ 到 $6$ 的整数，概率相等。
当你的整数严格小于 $N$ 时，重复以下操作:
- 投掷一次骰子。 如果骰子显示 $x$，将你的整数乘以 $x$。
找出你的整数最终成为 $N$ 的概率，取模 $998244353$。
如何求取模 $998244353$ 的概率？
我们可以证明所求概率总是有理数。 此外，在问题的限制下，当该值表示为 $\frac{P}{Q}$ 时，其中 $P$ 和 $Q$ 是两个互质的整数，我们可以证明存在唯一的整数 $R$，使得 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \leq R \lt 998244353$。 找出这个 $R$。约束
- $2 \leq N \leq 10^{18}$
- $N$ 是一个整数。
输入
从标准输入中输入以下格式的内容：
输出
打印出整数最终成为 $N$ 的概率，取模 $998244353$。
6
239578645
可能的一个过程如下所示。
- 初始时，你的整数为 $1$。
- 你投掷一次骰子，结果为 $2$。你的整数变为 $1 \times 2 = 2$。
- 你投掷一次骰子，结果为 $4$。你的整数变为 $2 \times 4 = 8$。
- 现在你的整数不小于 $6$，所以终止过程。
你的整数最终为 $8$，而不是 $N = 6$。
你的整数最终为 $6$ 的概率为 $\frac{7}{25}$。由于 $239578645 \times 25 \equiv 7 \pmod{998244353}$，输出 $239578645$。
7
0
无论骰子显示什么，你的整数都不会最终成为 $7$。
300
183676961
979552051200000000
812376310