#P16351. [2026年山东第二轮集训]数数题

[2026年山东第二轮集训]数数题

题目描述

对于一个正整数序列 aa,定义它的最大权独立集权值为:从 aa 中选择若干个互不相邻的数,使所选数字之和最大;这个最大值即为该序列的最大权独立集权值。

如果序列 aa 的最大权独立集权值恰好等于 aa 中所有数字之和的一半,则称 aa 是坏的;否则称 aa 是好的。

如果正整数序列 aa 的任意连续子区间都是好的,则称 aa 是极好的。

给定正整数 n,mn,m 以及 nn 个正整数集合

A1,A2,…,An,A_1,A_2,\ldots,A_n,

其中 nn 表示序列 aa 的长度,每个集合中的元素都属于 [1,m][1,m]。

求满足

ai∈Ai(1≤i≤n)a_i\in A_i\qquad (1\le i\le n)

的极好序列 aa 的数量。

答案对 998244353998244353 取模。

输入格式

第一行包含两个正整数 n,mn,m。

接下来 nn 行,第 ii 行包含 mm 个字符,每个字符均为 0 或 1,字符之间用一个空格隔开。

第 jj 个字符为 1,表示 j∈Aij\in A_i;否则表示 j∉Aij\notin A_i。

输出格式

输出一个整数,表示答案对 998244353998244353 取模后的结果。

样例输入

3 3
1 1 1
1 0 1
1 1 0

样例输出

4

数据范围与子任务

子任务 nn mm 特殊性质 分值
1 ≤10\le 10 ≤5\le 5 无 7
2 ≤200\le 200 ≤3\le 3 3
3 ≤4\le 4 对任意 i∈[1,n]i\in[1,n]、j∈[1,m]j\in[1,m],均有 j∈Aij\in A_i 5
4 无 20
5 ≤5\le 5 10
6 ≤6\le 6 5
7 ≤7\le 7 10
8 ≤12\le 12 5
9 ≤16\le 16 15
10 ≤19\le 19 20