No.1712 Read and Pile
タグ : / 解いたユーザー数 10
作問者 :
akakimidori
👑
hitonanode
Problem Statement
chinerist loves reading and owns $N$ books. These books are stacked vertically, and they are called book $i\ (1\le i \le N)$ in order from the top.
To read the $i$-th book from the top, chinerist consumes $i$ stamina to take the book out, and after finishing it, he puts it back on the stack at the $1$-st position from the top.
chinerist has decided to read $M$ times from now on. Which book to read the $i$-th time is represented by $-1$ or an integer from $1$ to $N$, $A_i\ (1\le i\le M)$: $A_i=-1$ means that the book to read has not been decided yet, and $A_i\neq -1$ means that it has been decided that book $A_i$ is read in the $i$-th reading.
For each reading whose book chinerist has not decided yet, he independently chooses a book uniformly at random from the $N$ books and reads it. Output the expected value of the stamina consumed over the $M$ readings, $\bmod 998244353$.
More precisely, it can be proved under the constraints of this problem that this value can be expressed as $\frac{P}{Q}$ using some coprime integers $P,\ Q$, and that there exists exactly $1$ integer $R\ (0 \le R < 998244353)$ satisfying $P \equiv Q\times R\ (\bmod 998244353)$.
Therefore, output $R$.
Input
$N$ $M$ $A_1$ $A_2$ $\dots$ $A_M$
- $1 \le N,M \le 2\times 10^5$
- $A_i=-1$ or $1 \le A_i \le N\ (1\le i \le M)$
- All input values are integers.
Output
Output the answer.
Print a newline at the end.
Sample
Sample 1
Input
3 5 2 3 1 3 1
Output
12
In this case, all the books chinerist reads are already decided.
The order of the books, from the top, changes as $(1,\ 2,\ 3)\rightarrow (2,\ 1,\ 3)\rightarrow (3,\ 2,\ 1)\rightarrow (1,\ 3,\ 2)\rightarrow (3,\ 1,\ 2)\rightarrow (1,\ 3,\ 2)$.
Thus the stamina consumed when taking out the books is, in order starting from the $1$-st reading, $2,\ 3,\ 3,\ 2,\ 2$, and the total is $12$.
Sample 2
Input
5 4 4 -1 3 -1
Output
798595496
One way to decide the books to read is, for example, to set $A_2=2,\ A_4=1$ (in this case, the total stamina consumed is $15$).
There are $25$ ways to decide in total, and the expected value of the total stamina consumed is $\frac{68}{5}$.
Sample 3
Input
12 23 2 7 -1 11 10 8 2 4 -1 -1 5 8 6 12 -1 11 -1 12 1 12 9 4 3
Output
925712622
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。