← 返回题目列表

AtCoder · abc215_h

H. 白菜大师

中文机器翻译题面 查看原题

分数: 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.