Home => ProblemSet => 100.2019-04:Emiya 家今天的饭
Problem1793--100.2019-04:Emiya 家今天的饭

1793: 100.2019-04:Emiya 家今天的饭

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 0
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

Input

第 1 行两个用单个空格隔开的整数 n,m。
第 2 行至第 n+1 行,每行 m 个用单个空格隔开的整数,其中第 i+1 行的 m 个数依次为 ai,1,ai,2,⋯,ai,m

Output

仅一行一个整数,表示所求方案数对 998,244,353 取模的结果。

Sample Input Copy

2 3 
1 0 1
0 1 1

Sample Output Copy

3

HINT

样例二:
输入:
3 3 
1 2 3 
4 5 0 
6 0 0
输出:
190


样例三:
输入:
5 5
1 0 0 1 1
0 1 0 1 0
1 1 1 1 0
1 0 1 0 1
0 1 1 0 1
输出:
742




【样例 1 解释】
由于在这个样例中,对于每组 i,j,Emiya 都最多只会做一道菜,因此我们直接通过给出烹饪方法、主要食材的编号来描述一道菜。
符合要求的方案包括:
  • 做一道用烹饪方法 1、主要食材 1 的菜和一道用烹饪方法 2、主要食材 2 的菜
  • 做一道用烹饪方法 1、主要食材 1 的菜和一道用烹饪方法 2、主要食材 3 的菜
  • 做一道用烹饪方法 1、主要食材 3 的菜和一道用烹饪方法 2、主要食材 2 的菜
因此输出结果为 3 mod 998,244,353=3。 需要注意的是,所有只包含一道菜的方案都是不符合要求的,因为唯一的主要食材在超过一半的菜中出现,这不满足 Yazid 的要求。
【样例 2 解释】
Emiya 必须至少做 2 道菜。
做 2 道菜的符合要求的方案数为 100。
做 3 道菜的符合要求的方案数为 90。
因此符合要求的方案数为 100 + 90 = 190。







Source/Category