Kuro and Topological Parity
Contest: Codeforces Round 482 (Div. 2)
Difficulty rating: 2400
Tags: dp

Kuro has recently won the "Most intelligent cat ever" contest. The three friends then decided to go to Katie's home to celebrate Kuro's winning. After a big meal, they took a small break then started playing games.

Kuro challenged Katie to create a game with only a white paper, a pencil, a pair of scissors and a lot of arrows (you can assume that the number of arrows is infinite). Immediately, Katie came up with the game called Topological Parity.

The paper is divided into $$$n$$$ pieces enumerated from $$$1$$$ to $$$n$$$. Shiro has painted some pieces with some color. Specifically, the $$$i$$$-th piece has color $$$c_{i}$$$ where $$$c_{i} = 0$$$ defines black color, $$$c_{i} = 1$$$ defines white color and $$$c_{i} = -1$$$ means that the piece hasn't been colored yet.

The rules of the game is simple. Players must put some arrows between some pairs of different pieces in such a way that for each arrow, the number in the piece it starts from is less than the number of the piece it ends at. Also, two different pieces can only be connected by at most one arrow. After that the players must choose the color ($$$0$$$ or $$$1$$$) for each of the unpainted pieces. The score of a valid way of putting the arrows and coloring pieces is defined as the number of paths of pieces of alternating colors. For example, $$$[1 \to 0 \to 1 \to 0]$$$, $$$[0 \to 1 \to 0 \to 1]$$$, $$$[1]$$$, $$$[0]$$$ are valid paths and will be counted. You can only travel from piece $$$x$$$ to piece $$$y$$$ if and only if there is an arrow from $$$x$$$ to $$$y$$$.

But Kuro is not fun yet. He loves parity. Let's call his favorite parity $$$p$$$ where $$$p = 0$$$ stands for "even" and $$$p = 1$$$ stands for "odd". He wants to put the arrows and choose colors in such a way that the score has the parity of $$$p$$$.

It seems like there will be so many ways which satisfy Kuro. He wants to count the number of them but this could be a very large number. Let's help him with his problem, but print it modulo $$$10^{9} + 7$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$p$$$ ($$$1 \leq n \leq 50$$$, $$$0 \leq p \leq 1$$$) — the number of pieces and Kuro's wanted parity.

The second line contains $$$n$$$ integers $$$c_{1}, c_{2}, ..., c_{n}$$$ ($$$-1 \leq c_{i} \leq 1$$$) — the colors of the pieces.

Output format:
Print a single integer — the number of ways to put the arrows and choose colors so the number of valid paths of alternating colors has the parity of $$$p$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, there are $$$6$$$ ways to color the pieces and add the arrows, as are shown in the figure below. The scores are $$$3, 3, 5$$$ for the first row and $$$5, 3, 3$$$ for the second row, both from left to right.

Example input:
3 1
-1 0 1

Example output:
6

Example input:
2 1
1 0

Example output:
1

Editorial:
The problem asks us to find the number of different simple directed acyclic graphs with $$$1 \to n$$$ forming its topological order to ensure the parity of the number of alternating paths to be equal to $$$p$$$. We will solve this problem using the dynamic programming approach.
Let's define even-white as the number of different nodes $$$u$$$ colored in white that has an even number of alternating paths that end in $$$u$$$. In the same fashion, let's define odd-white as the number of different nodes $$$u$$$ colored in white that has an odd number of alternating paths that end in $$$u$$$, even-black — the number of different nodes $$$u$$$ colored in black that has an even number of alternating paths that end in $$$u$$$, and odd-black — the number of different nodes $$$u$$$ colored in black that has an odd number of alternating paths that end in $$$u$$$. Let's also define $$$dp[i][ew][ow][eb]$$$ as the number of different graphs following the requirements that can be built using the first $$$i$$$ nodes, with $$$ew$$$ even-white nodes, $$$ow$$$ odd-white nodes and $$$eb$$$ even-black nodes (the number of odd-black nodes $$$ob = i - ew - ow - eb$$$). We will figure out how to calculate such value. For the sake of simplicity, let's consider the current node — the $$${i}^{th}$$$ node to be a white node.
We can notice a few things:
• If none of the previous $$$i - 1$$$ nodes connects to the current node, the current node becomes an odd-white node (the only alternating path that ends the current node is the node itself).
• How the previous white nodes connect to the current node does not matter. There are $$$2^{ow + ew - 1}$$$ ways to add edges between the previous white nodes and the current node.
• How the previous even-black nodes connect to the current node does not matter, as it does not change the state of the current white node (i.e. odd-white to even-white or even-white to odd-white). There are $$$2^{eb}$$$ ways to add edges between the previous even-black nodes and the current node.
• If there are an odd number of previous odd-black nodes that have edges to the current node, the current node becomes an even-white node. There are $$$\sum _{ k=0 }^{ \left\lfloor \frac { ob }{ 2 } \right\rfloor }{ ob \choose 2k+1 } $$$ ways to do this.
• If there are an even number of previous odd-black nodes that have edges to the current node, the current node becomes an odd-white node. There are $$$\sum _{ k=0 }^{ \left\lfloor \frac { ob }{ 2 } \right\rfloor }{ ob \choose 2k } $$$ ways to do this.
In conclusion, we can figure out that:
$$$dp[i][ew][ow][eb] = 2^{ow + ew - 1} \cdot (dp[i - 1][ew - 1][ow][eb] \cdot \sum _{ k=0 }^{ \left\lfloor \frac { ob }{ 2 } \right\rfloor }{ ob \choose 2k+1 } + dp[i - 1][ew][ow - 1][eb] \cdot \sum _{ k=0 }^{ \left\lfloor \frac { ob }{ 2 } \right\rfloor }{ ob \choose 2k })$$$
It is worth mentioning that we can use the same analogy to process when the current node is black.
In total, we process through $$$n^4$$$ states, with an $$$O(n)$$$ iteration for each stage, so the time complexity is $$$O(n^5)$$$. However, with precomputation of $$$\sum _{ k=0 }^{ \left\lfloor \frac { ob }{ 2 } \right\rfloor }{ ob \choose 2k+1 }$$$ and $$$\sum _{ k=0 }^{ \left\lfloor \frac { ob }{ 2 } \right\rfloor }{ ob \choose 2k }$$$ for every value of $$$ob$$$, we can optimize the time complexity to $$$O(n^4)$$$.
Time complexity: $$$O(n^4)$$$.