#1908. 黄焖鸡

    ID: 1908 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1962来源:qoj.ac数据:公开样例动态规划

黄焖鸡

黄焖鸡

题目描述

标题: 黄焖鸡 - Problem - QOJ.ac

#10306. 黄焖鸡

Statistics

题目背景

小 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