No.2579 Dice Sum Infinity (Modified Constraints Version)
問題文最終更新日: 2023-05-31 22:36:29
English (AI translation)
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$.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$".
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.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
noshi91