No.1741 Arrays and XOR Procedure
タグ : / 解いたユーザー数 106
作問者 :
nok0
とりゐ
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もしくは右上の雲マークをクリックしてアカウントを作成してください。