問題一覧 > 通常問題

No.2579 Dice Sum Infinity (Modified Constraints Version)

レベル : / AI推定難易度 : 3300 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 10
作問者 : noshi91 / テスター : noimi
お気に入りにしたユーザー ProblemId : 9550 / 自分の提出
問題文最終更新日: 2023-05-31 22:36:29
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
Advent Calendar Contest 2023 (順位表) の他の問題:

Original Problem

This problem is based on the following problem: https://atcoder.jp/contests/abc299/tasks/abc299_h

Problem Statement

You are given integers $M, K, R$. Let $P = 998244353$.
For an integer $A$, define $E _ A$ as follows.

Suppose that a variable $X$ initially satisfies $X = A$.
Roll a $K$-sided die and decrease $X$ by the number rolled. Repeat this, and let $E _ A$ be the expected number of die rolls until $X$ becomes a multiple of $M$.
Here, rolling a $K$-sided die yields each integer from $1$ to $K$ with equal probability.
It is guaranteed that only $M, K$ satisfying the following are given as input: "for every $A$, $E _ A$ can be represented as an irreducible fraction whose denominator is not divisible by $P$".
Representing $E _ R$ as an irreducible fraction $E _ R = a / b$, there exists a unique integer $x ~ (0 \leq x \lt P)$ such that $bx \equiv a \pmod P$. Output this value.

Input

$M\ K\ R$

  • $2 \leq M \lt P$
  • $1 \leq K \lt \min \lbrace 10 ^ 4, M \rbrace$
  • $0 \leq R \lt M$
  • For every $A$, $E _ A$ can be represented as an irreducible fraction whose denominator is not divisible by $P$

Output

$x$

Sample

Sample 1
Input
5 1 2
Output
2

Since the die has $1$ face, it always shows $1$. $X = 0$ is reached after exactly $2$ rolls, so $E _ 2 = 2$.

Sample 2
Input
4 2 1
Output
399297744

$E _ 1 = 14 / 5$.

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