No.1299 Random Array Score
nok0
zkou
Kite_kumaProblem Statement
You are given a sequence $A$ of $N$ elements. The $i$-th element of the sequence $A$ is $A_i$.
Perform the following operation exactly $K$ times.
Find the expected value of the sum of the elements of the sequence $A$ after the $K$ operations, and output it modulo $\bmod998244353$.
More precisely, it can be proved under the constraints of this problem that the expected value is a rational number, that is, it can be expressed as an irreducible fraction $\frac{P}{Q}$, and that an integer $R$ satisfying $R×Q≡P(\bmod 998244353),\ 0 \le R< 998244353$ is uniquely determined. Output this $R$.
Constraints
- All inputs are integers.
- $1 \le N\le 2 × 10^5$
- $0 \le K \le 10^{18}$
- $0 \le A_i \le 10^9$
Input
$N\ K$ $A_1\ A_2\ \dots \ A_N$
Output
Output the expected value of the sum of the elements of the sequence $A$ after the $K$ operations, modulo $\bmod 998244353$.
Sample
Sample 1
Input
3 1 1 2 3
Output
12
If $A_1$ is chosen in the operation, the sequence $A$ becomes $(1+1,2+1,3+1) = (2,3,4)$.
Similarly, if $A_2$ is chosen, the sequence $A$ becomes $(1+2,2+2,3+2) = (3,4,5)$.
Similarly, if $A_3$ is chosen, the sequence $A$ becomes $(1+3,2+3,3+3) = (4,5,6)$.
Therefore, the expected value of the sum of the sequence $A$ after $1$ operation is $\frac{(2 + 3 +4) + (3 + 4+5)+(4+5+6)}{3} = 12$.
Sample 2
Input
1 0 1
Output
1
It is possible that no operations are performed.
Sample 3
Input
10 1000000000000000000 3 1 4 1 5 9 2 6 5 3
Output
461591775
Output the value modulo $\bmod 998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。