問題一覧 > 通常問題

No.1741 Arrays and XOR Procedure

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 85
作問者 : ShirotsumeShirotsume / テスター : とりゐとりゐ nok0nok0
3 ProblemId : 7178 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-08 21:41:12

問題文

Shirotsume は長さ $N$ の数列 $A = [A_1, A_2, \dots A_N]$ を持っています。数列 $A$ の値は全て $0$ または $1$ です。

数列 $A$ に対して、以下の操作を考えます。

    操作:操作を行う前の数列 $A$ の長さを $M$ とする。数列 $A$ を数列 $A' = [(A_1\ \oplus\ A_2), (A_2\ \oplus\ A_3), (A_3\ \oplus\ A_4), ... (A_{M - 1}\ \oplus\ A_M)]$ に置き換える。

ただし、$a\ \oplus\ b$ は $a$ と $b$ の排他的論理和(XOR)を表します。

操作を $1$ 度行うと、数列は長さが $1$ 短くなります。数列 $A$ に操作を $N - 1$ 回繰り返し適用すると、$A$ は長さ $1$ の数列 $[0]$ または $[1]$ になります。

Shirotsume は長さが $N$ である数列 $A$ を一部隠して、長さ $N$ の数列 $B$ としてあなたに教えます。

数列 $B$ は $-1, 0, 1$ の値のみからなり、$1 ≤ i ≤ N$ について、$B_i = 0$ または$B_i = 1$ ならば $A_i = B_i$、$B_i = -1$ なら$A_i$ の値が隠されていることを表します。

$A$ の要素のうち隠されている要素の個数を $P$ とすると、$A$ としてありえる数列は $2^P$ 通りありますが、そのうち操作を $N - 1$ 回行った後 $A = [1]$ になるものは何通りありますか? $998244353$ で割ったあまりを求めてください。

制約

  • 入力は全て整数
  • $2 \leq N \leq 2 \times 10^5$
  • $B_i$ $(1 \leq i \leq N)$ の値は $-1, 0, 1$ のいずれか
  • $B_i \neq -1$ ならば、$A_i = B_i$
  • $B_i = -1$ であるものは、Shirotsume が数列 $A$ の $i$ 番目の要素を隠していることを意味する。

入力

入力は以下の形式で標準入力から与えられる。
$N$
$B_1$ $B_2$ $B_3$ $...$ $B_N$

出力

操作を $N - 1$ 回行った結果 $A = [1]$ になるものの個数を $998244353$ で割ったあまりを出力せよ。

最後に改行すること。

サンプル

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

隠されている要素 $2$ つのそれぞれに $0, 1$ を割り当てる方法は全部で $4$ 通りあります。そのそれぞれについて操作を行った結果を以下に示します。

$[0, 0, 1] → [(0\ \oplus\ 0), (0\ \oplus\ 1)] = [0, 1], [0, 1] → [(0\ \oplus\ 1)] = [1]$

$[0, 1, 1] → [(0\ \oplus\ 1), (1\ \oplus\ 1)] = [1, 0], [1, 0] → [(1\ \oplus\ 0)] = [1]$

$[1, 0, 1] → [(1\ \oplus\ 0), (0\ \oplus\ 1)] = [1, 1], [1, 1] → [(1\ \oplus\ 1)] = [0]$

$[1, 1, 1] → [(1\ \oplus\ 1), (1\ \oplus\ 1)] = [0, 0], [0, 0] → [(0\ \oplus\ 0)] = [0]$

サンプル2
入力
5
0 0 1 0 0
出力
0

Shirotsume が隠している要素の個数は $0$ であるかもしれません。また、すべての要素を隠しているかもしれません。

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

ここでは示しませんが、答えは非常に大きくなる場合があります。$998244353$ で割ったあまりを求めてください。

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