309980: CF1767C. Count Binary Strings
Memory Limit:512 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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.Input
题意翻译
有一个长度为 $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$。Output
题目大意:
给定一个整数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。
给定一个整数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。