問題一覧 > 通常問題

No.1712 Read and Pile

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 7
作問者 : chineristACchineristAC / テスター : akakimidoriakakimidori 👑 hitonanodehitonanode
1 ProblemId : 6045 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-10-18 19:55:04

問題文

chinerist 君は読書が大好きで、本を $N$ 冊持っています。これらの本は縦に積み上げられており、上から順に本 $i\ (1\le i \le N)$ とします。

chinerist 君は上から $i$ 番目の本を読む際、体力 $i$ を消費して本を取り出し、読み終えた後は $1$ 番上に積み上げて戻します。

chinerist 君はこれから $M$ 回読書をすることにしました。 $i$ 回目にどの本を読むかについては $-1$ または $1$ から $N$ の整数 $A_i\ (1\le i\le M)$ で表され、 $A_i=-1$ のとき読む本がまだ決まっていないことを、 $A_i\neq -1$ のとき $i$ 回目の読書では本 $A_i$ を読むことが決まっていることを表します。

chinerist 君がまだ読む本を決めていない部分についてはそれぞれ独立に、かつ $N$ 冊の中から一様ランダムに本を選んで読むとき、 $M$ 回の読書で 消費する体力の期待値を $\bmod 998244353$ で出力してください。

より正確には、この値はある互いに素な整数 $P,\ Q$ を用いて $\frac{P}{Q}$ と表せ、 $P \equiv Q\times R\ (\bmod 998244353)$ を満たす整数 $R\ (0 \le R < 998244353)$ がただ$1$ つ存在することがこの問題の制約下で証明できます。

よって $R$ を出力してください。

入力

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_M$
  • $1 \le N,M \le 2\times 10^5$
  • $A_i=-1$ または $1 \le A_i \le N\ (1\le i \le M)$
  • 与えられる入力はすべて整数

出力

答えを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3 5
2 3 1 3 1
出力
12

このケースでは chinerist 君が読む本はすべて決まっています。

本の並びは上から順に $(1,\ 2,\ 3)\rightarrow (2,\ 1,\ 3)\rightarrow (3,\ 2,\ 1)\rightarrow (1,\ 3,\ 2)\rightarrow (3,\ 1,\ 2)\rightarrow (1,\ 3,\ 2)$ と変化します。

よって本を取り出す時に消費する体力は $1$ 回目から順に $2,\ 3,\ 3,\ 2,\ 2$ となり、総和は $12$ です。

サンプル2
入力
5 4
4 -1 3 -1
出力
798595496

読む本の決め方としては、たとえば $A_2=2,\ A_4=1$ とする方法があります(この場合、消費する体力の総和は $15$ です)。

決め方は全部で $25$ 通り存在し、消費する体力の総和の期待値は $\frac{68}{5}$ です。

サンプル3
入力
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
出力
925712622

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。