問題一覧 > 通常問題

No.1712 Read and Pile

レベル : / AI推定難易度 : 2425 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 10
作問者 : chineristAC / テスター : akakimidori 👑 hitonanode
お気に入りにしたユーザー ProblemId : 6045 / 自分の提出
問題文最終更新日: 2021-10-18 19:55:04
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
yukicoder contest 318 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。