1442: Emiya 家今天的饭（2019 CCF CSP-S2 day2）
时间限制: 1 Sec 内存限制: 256 MB提交: 1 解决: 1
[提交] [状态] [讨论版] [命题人:]
题目描述
输入
第 1 行两个用单个空格隔开的整数 n, m。
第 2 行至第 n + 1 行，每行 m 个用单个空格隔开的整数，其中第 i + 1 行的 m 个 数依次为 ai,1, ai,2, . . . , ai,m。
第 2 行至第 n + 1 行，每行 m 个用单个空格隔开的整数，其中第 i + 1 行的 m 个 数依次为 ai,1, ai,2, . . . , ai,m。
输出
仅一行一个整数，表示所求方案数对 998, 244, 353 取模的结果。
样例输入 Copy
2 3
1 0 1
0 1 1
样例输出 Copy
3
提示
【样例1解释】
由于在这个样例中，对于每组i,j，Emiya都最多只会做一道菜，因此我们直接通过给出烹饪方法、主要食材的编号来描述一道菜。
符合要求的方案包括：
•做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材2的菜
•做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材3的菜
•做一道用烹饪方法1、主要食材3的菜和一道用烹饪方法2、主要食材2的菜
因此输出结果为3 mod 998,244,353=3。
需要注意的是，所有只包含一道菜的方案都是不符合要求的，因为唯一的主要食材在超过一半的菜中出现，这不满足Yazid的要求。
【样例2输入】
3 3
1 2 3
4 5 0
6 0 0
【样例2输出】
190
【样例2解释】
Emiya必须至少做2道菜。
做2道菜的符合要求的方案数为100。做3道菜的符合要求的方案数为90。
因此符合要求的方案数为100+90=190。
【样例3输入】
5 5
1 0 0 1 1
0 1 0 1 0
1 1 1 1 0
1 0 1 0 1 由于在这个样例中，对于每组i,j，Emiya都最多只会做一道菜，因此我们直接通过给出烹饪方法、主要食材的编号来描述一道菜。
符合要求的方案包括：
•做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材2的菜
•做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材3的菜
•做一道用烹饪方法1、主要食材3的菜和一道用烹饪方法2、主要食材2的菜
因此输出结果为3 mod 998,244,353=3。
需要注意的是，所有只包含一道菜的方案都是不符合要求的，因为唯一的主要食材在超过一半的菜中出现，这不满足Yazid的要求。
【样例2输入】
3 3
1 2 3
4 5 0
6 0 0
【样例2输出】
190
【样例2解释】
Emiya必须至少做2道菜。
做2道菜的符合要求的方案数为100。做3道菜的符合要求的方案数为90。
因此符合要求的方案数为100+90=190。
【样例3输入】
5 5
1 0 0 1 1
0 1 0 1 0
1 1 1 1 0
0 1 1 0 1
【样例3输出】
742
【样例4】
见选手目录下的meal/meal4.in 与meal/meal4.ans。
【样例5】
见选手目录下的meal/meal5.in 与meal/meal5.ans。
【数据范围】
|
测试点编号 |
n= |
m= |
ai,j< |
|
1 |
2 |
2 |
2 |
|
2 |
3 |
||
|
3 |
5 |
2 |
|
|
4 |
3 |
||
|
5 |
10 |
2 |
|
|
6 |
3 |
||
|
7 |
10 |
2 |
1000 |
|
8 |
3 |
||
|
9∼12 |
40 |
2 |
|
|
13∼16 |
3 |
||
|
17∼21 |
500 |
||
|
22∼25 |
100 |
2000 |
998,244,353 |