No.2391 SAN Value Check
タグ : / 解いたユーザー数 35
作問者 :
PCTprobability
/ テスター :
cleantted
tatyam
Mizar
👑 
amentorimaru
Problem Statement
You are given a positive integer $N$.
You have a real number $X$. Initially, $X=N$. You repeat the following operation while $X$ is at least $0$.
- Choose $1$ real number uniformly at random between $0$ and $1$, inclusive, and subtract it from $X$.
Let $A$ be the expected number of operations. Then there uniquely exists a sequence of rational numbers $(a_0,a_1,\dots,a_N)$ of length $N+1$ satisfying $A = \sum_{i=0}^{N} a_i e^i$, where $e$ is Napier's constant.
For $i = 0,1,\dots,N$, find $a_i \bmod 998244353$.
Definition of a rational number $\bmod\ 998244353$
It can be proved that $a_i(0 \le i \le N)$ is always a rational number. It can also be proved that, under the constraints of this problem, when the value is expressed as an irreducible fraction $\frac{P}{Q}$, we have $Q \neq 0 \pmod{998244353}$. Therefore, there uniquely exists an integer $R$ satisfying $R \times Q = P \pmod{998244353},0 \le R < 998244353$. Report this $R$.
Input
$N$
- $1 \le N \le 2 \times 10^5$
- $N$ is an integer.
Output
Print $N+1$ lines. On line $i(1 \le i \le N+1)$, print $a_{i-1} \bmod 998244353$.
Sample
Sample 1
Input
1
Output
0 1
The expected number of operations is $e$.
Sample 2
Input
2
Output
0 998244352 1
The expected number of operations is $e^2 - e$.
Sample 3
Input
3
Output
0 499122177 998244351 1
The expected number of operations is $e^3 - 2e^2 + \frac{e}{2}$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。