No.1239 Multiplication -2
eSeF
りあん問題文
長さ $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もしくは右上の雲マークをクリックしてアカウントを作成してください。