C - Catastrophic Roulette

Contest Duration: 2024-03-17(Sun) 12:00 - 2024-03-17(Sun) 14:00 (local time) (120 minutes) Back to Home

C - Catastrophic Roulette Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

整数 $1,2,\dots,N$ が均等な確率で出るルーレットがあります。
これを使って $2$ 人で以下のゲームを行います。

先攻と後攻が交互にルーレットを回す。
- 出た整数が今までに出ていないものであった場合、何も起こらない。
- そうでない場合、ルーレットを回したプレイヤーが罰金 $1$ 円を支払う。
$N$ 個の整数全てが少なくとも $1$ 度出たとき、直ちにゲームが終了する。

先攻後攻それぞれについて、ゲームが終了するまでに支払う罰金の期待値を $\text{mod}\ 998244353$ で求めてください。

期待値 $\text{mod } 998244353$ の定義

この問題で求める期待値は必ず有理数になることが証明できます。また、この問題の制約下では、求める期待値を既約分数 $\frac{y}{x}$ で表したときに $x$ が $998244353$ で割り切れないことが保証されます。

このとき $xz \equiv y \pmod{998244353}$ を満たすような $0$ 以上 $998244352$ 以下の整数 $z$ が一意に定まります。この $z$ を答えてください。

制約

$N$ は $1 \le N \le 10^6$ を満たす整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

出力

答えとして $2$ つの整数を出力せよ。
そのうち $1$ つ目は先攻が支払う罰金の期待値、 $2$ つ目は後攻が支払う罰金の期待値をそれぞれ $\text{mod}\ 998244353$ で表現した整数である。

入力例 1Copy

Copy

出力例 1Copy

Copy

0 0

この入力では $N=1$ です。
先攻がルーレットを回すと必ず $1$ が出て、直ちにゲームが終了します。
よって、支払う罰金の期待値は先攻後攻ともに $0$ です。

入力例 2Copy

Copy

出力例 2Copy

Copy

332748118 665496236

この入力では $N=2$ です。ゲームの進行の一例は以下の通りです。

先攻がルーレットを回し、 $2$ が出た。この時、何も起こらない。
後攻がルーレットを回し、 $2$ が出た。この時、後攻は罰金 $1$ 円を支払う。
先攻がルーレットを回し、 $2$ が出た。この時、先攻は罰金 $1$ 円を支払う。
後攻がルーレットを回し、 $1$ が出た。この時、何も起こらない。
この時点で $1,2$ が少なくとも $1$ 度出たので、直ちにゲームが終了する。
このようにゲームが進行した場合、先攻が支払う罰金は $1$ 円、後攻が支払う罰金も $1$ 円となります。

先攻が支払う罰金の期待値は $\frac{1}{3}$ 円、後攻が支払う罰金の期待値は $\frac{2}{3}$ 円であることが示せます。

入力例 3Copy

Copy

出力例 3Copy

Copy

174692763 324429416

Points: $500$ points

Problem Statement

There is a roulette that produces an integer from $1,2,\dots,N$ with equal probability.
Two players use it to play the following game:

The players take turns spinning the roulette.
- If the produced integer has not appeared before, nothing happens.
- Otherwise, the player who spun the roulette pays a fine of $1$ yen.
The game immediately ends when all of the $N$ integers have appeared at least once.

For each of the first and second players, find the expected value of the amount of the fine paid before the game ends, modulo $998244353$ .

On expected values modulo $998244353$

It can be proved that the expected values sought in this problem are always rational numbers. Furthermore, under the constraints of this problem, when the expected values are expressed as irreducible fractions $\frac{y}{x}$ , it is guaranteed that $x$ is not divisible by $998244353$ .

Now, there is a unique integer $z$ between $0$ and $998244352$ , inclusive, such that $xz \equiv y \pmod{998244353}$ . Provide this $z$ as the answer.

Constraints

$N$ is an integer such that $1 \le N \le 10^6$ .

Input

The input is given from Standard Input in the following format:

$N$

Output

Print two integers as the answer.
The first is the expected value of the amount of the fine paid by the first player, and the second is the expected value of the amount of the fine paid by the second player, represented as integers modulo $998244353$ .

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

0 0

In this input, $N=1$ .
When the first player spins the roulette, it always produces $1$ , ending the game immediately.
Thus, the expected values of the amounts of the fines paid by the first and second players are both $0$ .

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy

332748118 665496236

In this input, $N=2$ . Here is a possible progression of the game:

The first player spins the roulette, and it produces $2$ . Nothing happens.
The second player spins the roulette, and it produces $2$ . The second player pays a fine of $1$ yen.
The first player spins the roulette, and it produces $2$ . The first player pays a fine of $1$ yen.
The second player spins the roulette, and it produces $1$ . Nothing happens.
At this point, both $1$ and $2$ have appeared at least once, so the game immediately ends.
In this progression, the amount of the fine paid by the first player is $1$ yen, and the amount of the fine paid by the second player is also $1$ yen.

It can be shown that the expected value of the amount of the fine paid by the first player is $\frac{1}{3}$ yen, and the expected value of the amount of the fine paid by the second player is $\frac{2}{3}$ yen.

Sample Input 3Copy

Copy

Sample Output 3Copy

Copy

174692763 324429416