#1908. 黄焖鸡
黄焖鸡
黄焖鸡
题目描述
标题: 黄焖鸡 - Problem - QOJ.ac
#10306. 黄焖鸡
题目背景
小 F 喜欢吃黄焖鸡。但是有一天他发现,有神秘人在他去往食堂的路上设置了无法跨过的障碍;只有解决下面的问题,障碍才能消失。
题目描述
对于一个正整数序列 a,定义 a 的最大权独立集的权值为从 a 中选择若干不相邻的数,选出的数的和的最大值。(相邻的定义:设 n 为 a 的长度,则对于 1≤i<n,位置 i 和位置 i+1 相邻,其它均不相邻)
如果 a 的最大权独立集权值的两倍刚好是 a 中所有数的和,就说 a 是坏的;否则就说 a 是好的。
若正整数序列 a 的任何子区间都是好的,就说 a 是极好的。(子区间的定义:设 a 的长度为 n,则 ∀1≤l≤r≤n,[al,al+1,…,ar] 称为 a 的一个子区间)
给定 n,m 和 n 个正整数集合 A1∼An,n 表示 a 的长度,集合中的数都属于 [1,m]。问:如果对于每个 i,ai 都可以在 Ai 中任取,有多少种方案可以使得 a 是极好的。答案对 998244353 取模。
输入格式
从标准输入读入数据。
输入的第一行是两个正整数 n,m,用一个空格隔开。
接下来 n 行,第 i (1≤i≤n) 行有 m 个字符,每个字符都是 0 或 1,第 j (1≤j≤m) 个字符如果是 1,表示 j∈Ai,否则表示 j∉Ai。字符之间用一个空格隔开。
输出格式
输出到标准输出。
输出答案模 998244353 的值。
样例数据
样例 1 输入
3 3
1 1 1
1 0 1
1 1 0
样例 1 输出
4
样例 1 解释
本样例中,A1={1,2,3},A2={1,3},A3={1,2},极好的序列有以下几种:
- [1,3,1]
- [2,1,2]
- [2,3,2]
- [3,1,2]
子任务
所有数据均满足:1≤n≤200,1≤m≤19。
子任务 n m 特殊性质 分数 1 ≤10 ≤5 无 7 2 ≤200 ≤3 3 3 ≤4 ∀1≤i≤n,∀1≤j≤m,都有 j∈Ai 5 4 ≤4 无 20 5 ≤5 10 6 ≤6 5 7 ≤7 10 8 ≤12 5 9 ≤16 15 10 ≤19 20
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 3
1 1 1
1 0 1
1 1 0
4