問題一覧 > 通常問題

No.2579 Dice Sum Infinity (制約変更版)

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 9
作問者 : noshi91 / テスター : noimi
2 ProblemId : 9550 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-05-31 22:36:29

元ネタ

この問題の元ネタはhttps://atcoder.jp/contests/abc299/tasks/abc299_hこの問題です。

問題文

整数 M,K,RM, K, R が与えられます。また、P=998244353P = 998244353 とします。
整数 AA に対して EAE _ A を以下のように定めます。

変数 XX が最初 X=AX = A を満たすとする。
KK 面のサイコロを振り出目の分だけ XX を減らす。 これを繰り返し、XX が MM の倍数になるまでにサイコロを振った回数の期待値を EAE _ A とする。
ただし、KK 面のサイコロを振ると 11 以上 KK 以下の整数が同様に確からしい確率で出るとする。
「すべての AA に対して、EAE _ A は分母が PP で割り切れない既約分数で表される」を満たす M,KM, K だけが入力で与えられることが保証されます。
ERE _ R を既約分数で表して ER=a/bE _ R = a / b としたとき、bx≡a(modP)bx \equiv a \pmod P を満たす整数 x (0≤x<P)x ~ (0 \leq x \lt P) が一意に存在するので、それを出力してください。

入力

M K RM\ K\ R

  • 2≤M<P2 \leq M \lt P
  • 1≤K<min⁡{104,M}1 \leq K \lt \min \lbrace 10 ^ 4, M \rbrace
  • 0≤R<M0 \leq R \lt M
  • すべての AA に対して、EAE _ A は分母が PP で割り切れない既約分数で表される

出力

xx

サンプル

サンプル1
入力
5 1 2
出力
2

11 面のサイコロなので、必ず 11 の目が出ます。 丁度 22 回で X=0X = 0 となるため、E2=2E _ 2 = 2 です。

サンプル2
入力
4 2 1
出力
399297744

E1=14/5E _ 1 = 14 / 5 です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。