CF1767C Count Binary Strings

给定一个整数 $n$。你需要计算满足以下约束条件的二进制字符串（仅由字符 $0$ 和/或 $1$ 组成）$s$ 的数量。 对于每一对整数 $(i, j)$，其中 $1 \le i \le j \le n$，给定一个整数 $a_{i,j}$。它对字符串 $s_i s_{i+1} s_{i+2} \dots s_j$ 施加如下约束： - 如果 $a_{i,j} = 1$，则 $s_i s_{i+1} s_{i+2} \dots s_j$ 中所有字符必须相同； - 如果 $a_{i,j} = 2$，则 $s_i s_{i+1} s_{i+2} \dots s_j$ 中必须至少有两个不同的字符； - 如果 $a_{i,j} = 0$，则 $s_i s_{i+1} s_{i+2} \dots s_j$ 没有额外约束。 请计算满足上述所有约束条件的长度为 $n$ 的二进制字符串 $s$ 的数量。由于答案可能很大，请输出对 $998244353$ 取模后的结果。

第一行包含一个整数 $n$（$2 \le n \le 100$）。 接下来有 $n$ 行。第 $i$ 行包含 $n-i+1$ 个整数，分别为 $a_{i,i}, a_{i,i+1}, a_{i,i+2}, \dots, a_{i,n}$（$0 \le a_{i,j} \le 2$）。

输出一个整数，表示满足所有约束条件的字符串数量，对 $998244353$ 取模。

在第一个样例中，满足条件的字符串有 001、010、011、100、101、110。 在第二个样例中，满足条件的字符串有 001、110。 由 ChatGPT 4.1 翻译