問題一覧 > 通常問題

No.3044 The Usual Frog

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 51
作問者 : Blue_S / テスター : nauclhlt eiram naniwazu
お気に入りにしたユーザー ProblemId : 11836 / 自分の提出
問題文最終更新日: 2025-02-26 18:28:46
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 458 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。