分数: 600 点
问题陈述
卷心菜种植户高桥已经长大了 N 卷心菜品牌,称为品牌 1 通过品牌 N。他有 A_i 品牌白菜头 i (1 \leq i \leq N)。在这里, 所有的卷心菜头都是可区分的。
他有 M 客户致电公司 1 通过公司 M。公司简介 j (1 \leq j \leq M) 已订购 B_j 卷心菜头。
不同的公司接受不同品牌的卷心菜。对于每对 i, j (1 \leq i \leq N, 1 \leq j \leq M),
- if c_{i, j} = 1, 品牌白菜 i 可以运送到公司 j;
- if c_{i, j} = 0, 品牌白菜 i 无法运送至公司 j.
如果高桥成功决定将卷心菜头运送到哪里,他将被称为“卷心菜大师” B_j 或更多的卷心菜将被运送到每个公司 j (1 \leq j \leq M).
Snuke决定选择并吃掉零颗或更多头的卷心菜,这样高桥无论将卷心菜运送到哪里,都无法获得卷心菜大师的称号。他不太喜欢白菜,所以他会选择吃 最小值 达到他的目标需要多少颗卷心菜。
打印 Snuke 会吃的白菜头数,以及方式数,取模 998244353,让 Snuke 选择白菜头来吃。当有一个卷心菜可以用一种方法吃而不能用另一种方法吃时,两种选择卷心菜的方法被认为是不同的。在这里,记住任意两颗卷心菜都是 即使是同一品牌也能区分.
约束
- 1 \leq N \leq 20
- 1 \leq M \leq 10^4
- 1 \leq A_i \leq 10^5
- 1 \leq B_j \leq 10^5
- c_{i, j} \in \lbrace 0, 1 \rbrace
- 对于每个 1 \leq j \leq M,存在 1 \leq i \leq N 这样 c_{i, j} = 1.
- 输入中的所有值都是整数。 您选择的
输入
输入由标准输入按以下格式给出:
N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M
c_{1, 1} c_{1, 2} \ldots c_{1, M}
c_{2, 1} c_{2, 2} \ldots c_{2, M}
\vdots
c_{N, 1} c_{N, 2} \ldots c_{N, M}
输出
打印 X,Snuke 会吃掉的卷心菜头数,以及 Y,Snuke选择白菜头吃的方式数,取模 998244353,按此顺序,中间有一个空格。
X Y
示例输入 1
3 2 2 2 5 3 4 1 0 1 1 0 1
示例输出 1
2 6
Snuke会吃掉两颗卷心菜,以防止高桥成为卷心菜大师。这样选择白菜头吃的方法有六种,如下图,其中 (i, j) 表示 j品牌白菜头 i.
- (1, 1), (1, 2)
- (1, 1), (2, 1)
- (1, 1), (2, 2)
- (1, 2), (2, 1)
- (1, 2), (2, 2)
- (2, 1), (2, 2)
示例输入 2
1 1 3 4 1
示例输出 2
0 1
即使斯努克不吃卷心菜,高桥也有可能无法成为卷心菜大师。 然后,Snuke 会吃零头白菜,而他选择吃白菜头的方法只有一种:不吃任何东西。
示例输入 3
1 3 100 30 30 30 1 1 1
示例输出 3
11 892328666
对于 Snuke 选择吃白菜头的方式数,一定要打印模数 998244353.