No.3044 The Usual Frog
Problem Statement
There are a total of
$10^{10000}$
platforms, numbered from
$1$
to
$10^{10000}$.
A frog rolls a fair $6$-sided die and moves forward by 1 platform if the result is less than
$k$,
by 2 platforms if the result is at least
$k$
and less than
$l$,
and by
$T$ platforms if the result is at least
$l$.
Starting from platform
$1$,
the frog rolled the die
$10^{100}$
times and moved along the platforms according to the results.
Find the probability that the frog stopped exactly on platform
$N$
during this process.
It can be proved that the answer is a rational number.
Writing the answer as
$\frac{P}{Q}$,
there uniquely exists an integer
$0 \le R \lt 998244353$
such that
$QR \equiv P \mod 998244353$.
Output this
$R$.
Input
$N\ T$ $k\ l$
$1 \le N \le 10^9$
$2 \lt T \lt 100$
$1 \le k \le l \le 7$
Output
$ans$Print a newline at the end.
Sample
Sample 1
Input
3 5 4 6
Output
83187030
This equals the probability of rolling $1$ for the first $2$ times or rolling $2$ first, so it is $(3 / 6) ^ 2 + (2 / 6) = 7 / 12$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
nauclhlt
naniwazu