問題一覧 > 通常問題

No.1239 Multiplication -2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 79
作問者 : eSeFeSeF / テスター : りあんりあん
10 ProblemId : 5123 / 出題時の順位表
問題文最終更新日: 2020-09-25 18:10:10

問題文

長さ $N$ の整数列 $a$ が与えられます。 これを非空な $1$ 個以上の連続部分列に分割する方法は $2^{N-1}$ 通りありますが、 そのような方法のうち $1$ つを無作為に選ぶとき、「分割されてできた部分列のうち、要素全ての積が $-2$ であるようなものの個数」の期待値を求めてください。

答えは有理数 $\dfrac{P}{Q}\ (Q\neq 0)$ として表せることが示せるので、 これを $\bmod 998244353$ での表現、 即ち $E\times Q\equiv P\ \pmod{998244353}$、$0\le E\lt 998244353$ を満たす整数 $E$ として出力してください。

入力

$N$
$a_1\ \cdots \ a_N$
【制約】
  • $1\le N\le 2\times 10^5$
  • $|a_i|\le 2$
  • 入力は全て整数

出力

期待値を $\bmod 998244353$ で出力せよ。

サンプル

サンプル1
入力
3
-2 1 -2
出力
499122178

分割方法は $4$ 通りあり、それぞれ

  • $\{ -2,1,-2\}$
  • $\{ -2\},\ \{ 1,-2\}$
  • $\{ -2,1\} ,\ \{ -2\}$
  • $\{ -2\} ,\ \{ 1\} ,\ \{ -2\}$

となります。それぞれ要素全ての積が $-2$ であるような部分列は $0$ 個、$2$ 個、$2$ 個、$2$ 個であり、 これらが等確率で選ばれるので、期待値は $\dfrac{3}{2}$ です。

$499122178\times 2\equiv 3\ \pmod{998244353}$ なので、$499122178$ を出力してください。

サンプル2
入力
4
-1 -1 0 2
出力
0

どのように分割しても、積が $-2$ になるような部分列は存在しません。 よって、期待値は $0$ です。

サンプル3
入力
8
0 -2 0 -2 0 -2 -1 -1
出力
124780545

期待値は $\dfrac{7}{8}$ です。

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