样例二:
输入:
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。