Count Binary Strings

题意翻译

有一个长度为 $n$ 的 01 串 $s$（下标从 $1$ 开始）和一些限制 $a_{i,j}(1 \le i \le j \le n)$。 $a_{i,j}$ 的含义如下： | $a_{i,j}=$ | 含义 | | :----------: | :----------: | | $0$ | 没有限制 | | $1$ | 对于所有的 $i \le p \le q \le j$ 均有 $s_p=s_q$ | | $2$ | 存在 $i \le p \le q \le j$ 使得 $s_p \neq s_q$ | 求可能的 $s$ 的个数。**答案对 $998244353$ 取模。** ------------ 对于 $100\%$ 的数据，$2 \le n \le 100$，$0 \le a_{i,j} \le 2$。

题目描述

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 $ .

输入输出格式

输入格式

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 $ ).

输出格式

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

输入输出样例

输入样例 #1

3
1 0 2
1 0
1

输出样例 #1

6

输入样例 #2

3
1 1 2
1 0
1

输出样例 #2

2

输入样例 #3

3
1 2 1
1 0
1

输出样例 #3

0

输入样例 #4

3
2 0 2
0 1
1

输出样例 #4

0

说明

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.

题目大意：
给定一个整数n，求满足以下条件的长度为n的二进制字符串s的个数：对于每对整数(i, j)（1≤i≤j≤n），给定一个整数$a_{i,j}$，它对字符串$s_is_{i+1}s_{i+2}…s_j$施加以下限制：

- 如果$a_{i,j}=1$，$s_is_{i+1}s_{i+2}…s_j$中的所有字符都应该相同；
- 如果$a_{i,j}=2$，$s_is_{i+1}s_{i+2}…s_j$中应该至少有两个不同的字符；
- 如果$a_{i,j}=0$，对字符串$s_is_{i+1}s_{i+2}…s_j$没有额外的限制。

计算满足上述条件的长度为n的二进制字符串s的个数。由于答案可能很大，以998244353为模输出。

输入输出数据格式：
输入格式：
第一行包含一个整数n（2≤n≤100）。

然后是n行。第i行包含n-i+1个整数$a_{i,i}, a_{i,i+1}, a_{i,i+2}, …, a_{i,n}$（0≤$a_{i,j}$≤2）。

输出格式：
打印一个整数——满足约束的字符串的数量，模998244353。题目大意： 给定一个整数n，求满足以下条件的长度为n的二进制字符串s的个数：对于每对整数(i, j)（1≤i≤j≤n），给定一个整数$a_{i,j}$，它对字符串$s_is_{i+1}s_{i+2}…s_j$施加以下限制： - 如果$a_{i,j}=1$，$s_is_{i+1}s_{i+2}…s_j$中的所有字符都应该相同； - 如果$a_{i,j}=2$，$s_is_{i+1}s_{i+2}…s_j$中应该至少有两个不同的字符； - 如果$a_{i,j}=0$，对字符串$s_is_{i+1}s_{i+2}…s_j$没有额外的限制。 计算满足上述条件的长度为n的二进制字符串s的个数。由于答案可能很大，以998244353为模输出。 输入输出数据格式： 输入格式： 第一行包含一个整数n（2≤n≤100）。 然后是n行。第i行包含n-i+1个整数$a_{i,i}, a_{i,i+1}, a_{i,i+2}, …, a_{i,n}$（0≤$a_{i,j}$≤2）。 输出格式： 打印一个整数——满足约束的字符串的数量，模998244353。