問題一覧 > 通常問題

No.1741 Arrays and XOR Procedure

レベル : / AI推定難易度 : 1250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 106
作問者 : Shirotsume / テスター : nok0 とりゐ
お気に入りにしたユーザー ProblemId : 7178 / 自分の提出
問題文最終更新日: 2023-04-08 19:28:09
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 322 (順位表) の他の問題:

Problem Statement

Shirotsume has a sequence $A = [A_1, A_2, \dots A_N]$ of length $N$. All values of the sequence $A$ are $0$ or $1$.

Consider the following operation on the sequence $A$.

    Operation: Let $M$ be the length of the sequence $A$ before the operation. Replace the sequence $A$ with the sequence $A' = [(A_1\ \oplus\ A_2), (A_2\ \oplus\ A_3), (A_3\ \oplus\ A_4), ... (A_{M - 1}\ \oplus\ A_M)]$.

Here, $a\ \oplus\ b$ denotes the bitwise exclusive OR (XOR) of $a$ and $b$.

Performing the operation $1$ time makes the sequence shorter by $1$. Applying the operation to the sequence $A$ repeatedly $N - 1$ times turns $A$ into a sequence of length $1$, either $[0]$ or $[1]$.

Shirotsume hides some parts of the sequence $A$ of length $N$ and tells it to you as a sequence $B$ of length $N$.

The sequence $B$ consists only of the values $-1, 0, 1$. For $1 ≤ i ≤ N$, if $B_i = 0$ or $B_i = 1$ then $A_i = B_i$, and if $B_i = -1$ then the value of $A_i$ is hidden.

Let $P$ be the number of hidden elements of $A$. There are $2^P$ possible sequences for $A$. How many of them become $A = [1]$ after performing the operation $N - 1$ times? Find the count modulo $998244353$.

Constraints

  • All inputs are integers.
  • $2 \leq N \leq 2 \times 10^5$
  • The value of $B_i$ $(1 \leq i \leq N)$ is one of $-1, 0, 1$.

Input

The input is given from Standard Input in the following format.
$N$
$B_1$ $B_2$ $B_3$ $...$ $B_N$

Output

Print the number of sequences that become $A = [1]$ as a result of performing the operation $N - 1$ times, modulo $998244353$.

Print a newline at the end.

Sample

Sample 1
Input
3
-1 -1 1
Output
2

There are $4$ ways in total to assign $0, 1$ to each of the $2$ hidden elements. The results of performing the operations for each of them are shown below.

$[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]$

Sample 2
Input
5
0 0 1 0 0
Output
0

The number of elements Shirotsume hides may be $0$. Shirotsume may also hide all of the elements.

Sample 3
Input
7
-1 0 1 0 1 1 -1
Output
2

Although not shown here, the answer can be very large. Find it modulo $998244353$.

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