No.2579 Dice Sum Infinity (制約変更版)
レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 9
作問者 :
noshi91
/ テスター :
noimi
タグ : / 解いたユーザー数 9
作問者 :
noshi91
/ テスター :
noimi
問題文最終更新日: 2023-05-31 22:36:29
元ネタ
この問題の元ネタはhttps://atcoder.jp/contests/abc299/tasks/abc299_hこの問題です。
問題文
整数 $M, K, R$ が与えられます。また、$P = 998244353$ とします。
整数 $A$ に対して $E _ A$ を以下のように定めます。
変数 $X$ が最初 $X = A$ を満たすとする。「すべての $A$ に対して、$E _ A$ は分母が $P$ で割り切れない既約分数で表される」を満たす $M, K$ だけが入力で与えられることが保証されます。
$K$ 面のサイコロを振り出目の分だけ $X$ を減らす。 これを繰り返し、$X$ が $M$ の倍数になるまでにサイコロを振った回数の期待値を $E _ A$ とする。
ただし、$K$ 面のサイコロを振ると $1$ 以上 $K$ 以下の整数が同様に確からしい確率で出るとする。
$E _ R$ を既約分数で表して $E _ R = a / b$ としたとき、$bx \equiv a \pmod P$ を満たす整数 $x ~ (0 \leq x \lt P)$ が一意に存在するので、それを出力してください。
入力
$M\ K\ R$
- $2 \leq M \lt P$
- $1 \leq K \lt \min \lbrace 10 ^ 4, M \rbrace$
- $0 \leq R \lt M$
- すべての $A$ に対して、$E _ A$ は分母が $P$ で割り切れない既約分数で表される
出力
$x$
サンプル
サンプル1
入力
5 1 2
出力
2
$1$ 面のサイコロなので、必ず $1$ の目が出ます。 丁度 $2$ 回で $X = 0$ となるため、$E _ 2 = 2$ です。
サンプル2
入力
4 2 1
出力
399297744
$E _ 1 = 14 / 5$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。