Count Binary Strings
Contest: Educational Codeforces Round 140 (Rated for Div. 2)
Difficulty rating: 2100
Tags: data structures, dp

You are given an integer $$$n$$$. You have to calculate the number of binary (consisting of characters 0 and/or 1) strings $$$s$$$ meeting the following constraints.

For every pair of integers $$$(i, j)$$$ such that $$$1 \le i \le j \le n$$$, an integer $$$a_{i,j}$$$ is given. It imposes the following constraint on the string $$$s_i s_{i+1} s_{i+2} \dots s_j$$$:

- if $$$a_{i,j} = 1$$$, all characters in $$$s_i s_{i+1} s_{i+2} \dots s_j$$$ should be the same;
- if $$$a_{i,j} = 2$$$, there should be at least two different characters in $$$s_i s_{i+1} s_{i+2} \dots s_j$$$;
- if $$$a_{i,j} = 0$$$, there are no additional constraints on the string $$$s_i s_{i+1} s_{i+2} \dots s_j$$$.

Count the number of binary strings $$$s$$$ of length $$$n$$$ meeting the aforementioned constraints. Since the answer can be large, print it modulo $$$998244353$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 100$$$).

Then $$$n$$$ lines follow. The $$$i$$$-th of them contains $$$n-i+1$$$ integers $$$a_{i,i}, a_{i,i+1}, a_{i,i+2}, \dots, a_{i,n}$$$ ($$$0 \le a_{i,j} \le 2$$$).

Output format:
Print one integer — the number of strings meeting the constraints, taken modulo $$$998244353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first example, the strings meeting the constraints are 001, 010, 011, 100, 101, 110.

In the second example, the strings meeting the constraints are 001, 110.

Example input:
3
1 0 2
1 0
1

Example output:
6

Example input:
3
1 1 2
1 0
1

Example output:
2

Editorial:
Suppose we build the string from left to right, and when we place the $$$i$$$-th character, we ensure that all substrings ending with the $$$i$$$-th character are valid. What do we need to know in order to calculate the number of different characters in the string ending with the $$$i$$$-th character?
Suppose the character $$$s_i$$$ is 0. Let's try going to the left of it. The string from $$$i$$$ to $$$i$$$ will have the same characters; but if there is at least one character 1 before the $$$i$$$-th position, the string $$$s_1 s_2 s_3 \dots s_i$$$ will have two different characters. What about the strings in the middle? The string $$$s_j s_{j+1} \dots s_i$$$ will contain different characters if and only if there is at least one 1 in $$$[j, i)$$$ (since $$$s_i$$$ is 0), so we are actually interested in the position of the last character 1 before $$$i$$$.
The same logic applies if the character $$$s_i$$$ is 1: we are only interested in the position of the last 0 before $$$i$$$, and it is enough to check if all substrings ending with the $$$i$$$-th character are violated.
What if when we choose the $$$i$$$-th character, we violate some substring that doesn't end in the $$$i$$$-th position? Well, you could also check that... or you could just ignore it. Actually, it doesn't matter if this happens because it means that the substring that is violated ends in some position $$$k > i$$$; and we will check it when placing the $$$k$$$-th character.
So, the solution can be formulated with the following dynamic programming: let $$$dp_{i,j}$$$ be the number of ways to choose the first $$$i$$$ characters of the string so that the last character different from $$$s_i$$$ was $$$s_j$$$ (or $$$j = 0$$$ if there was no such character), and all the constraints on the substrings ending no later than position $$$i$$$ are satisfied. The transitions are simple: you either place the same character as the last one (going from $$$dp_{i,j}$$$ to $$$dp_{i+1,j}$$$), or a different character (going from $$$dp_{i,j}$$$ to $$$dp_{i+1,i}$$$); and when you place a character, you check all the constraints on the substrings ending with the $$$i$$$-th position. Note that the state $$$dp_{1,0}$$$ is actually represented by two strings: 0 and 1.
This solution works in $$$O(n^3)$$$, although $$$O(n^4)$$$ or $$$O(n^2)$$$ implementations are also possible.