103004: [Atcoder]ABC300 E - Dice Product 3
Description
Score : $500$ points
Problem Statement
You have an integer $1$ and a die that shows integers between $1$ and $6$ (inclusive) with equal probability.
You repeat the following operation while your integer is strictly less than $N$:
- Cast a die. If it shows $x$, multiply your integer by $x$.
Find the probability, modulo $998244353$, that your integer ends up being $N$.
How to find a probability modulo $998244353$?
We can prove that the sought probability is always rational. Additionally, under the constraints of this problem, when that value is represented as $\frac{P}{Q}$ with two coprime integers $P$ and $Q$, we can prove that there is a unique integer $R$ such that $R \times Q \equiv P\pmod{998244353}$ and $0 \leq R \lt 998244353$. Find this $R$.Constraints
- $2 \leq N \leq 10^{18}$
- $N$ is an integer.
Input
The input is given from Standard Input in the following format:
$N$
Output
Print the probability, modulo $998244353$, that your integer ends up being $N$.
Sample Input 1
6
Sample Output 1
239578645
One of the possible procedures is as follows.
- Initially, your integer is $1$.
- You cast a die, and it shows $2$. Your integer becomes $1 \times 2 = 2$.
- You cast a die, and it shows $4$. Your integer becomes $2 \times 4 = 8$.
- Now your integer is not less than $6$, so you terminate the procedure.
Your integer ends up being $8$, which is not equal to $N = 6$.
The probability that your integer ends up being $6$ is $\frac{7}{25}$. Since $239578645 \times 25 \equiv 7 \pmod{998244353}$, print $239578645$.
Sample Input 2
7
Sample Output 2
0
No matter what the die shows, your integer never ends up being $7$.
Sample Input 3
300
Sample Output 3
183676961
Sample Input 4
979552051200000000
Sample Output 4
812376310
Input
题意翻译
你有一个整数 $1$ 和一个等概率显示 $1$ 到 $6$ 的整数的骰子。当你的整数严格小于 $N$ 时，你重复下面的操作： + 投这个骰子。如果它显示的是 $x$，就用你的整数乘以 $x$。 找出你的整数最后是 $N$ 的概率，模 $998244353$。Output
问题描述
你有一个整数1和一个骰子，骰子显示1到6（包括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$
输出
输出你的整数最终等于N的概率，对998244353取模。
样例输入1
6
样例输出1
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。
样例输入2
7
样例输出2
0
无论骰子显示什么，你的整数永远不会变为7。
样例输入3
300
样例输出3
183676961
样例输入4
979552051200000000
样例输出4
812376310