H - Cabbage Master 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

キャベツ農家の高橋君は、品種 1 から品種 N までの N 種類のキャベツを育てました。高橋君は品種 i (1 \leq i \leq N) のキャベツを A_i 個持っています。ここで、 すべてのキャベツは区別できます。
キャベツの卸先として会社 1 から会社 M までの M 個の会社があり、会社 j (1 \leq j \leq M) からは B_j 個のキャベツの注文を受けています。
出荷できるキャベツの品種は会社ごとに異なっており、すべての i, j の組 (1 \leq i \leq N, 1 \leq j \leq M) について

  • c_{i, j} = 1 のとき、品種 i のキャベツを会社 j に出荷できます。
  • c_{i, j} = 0 のとき、品種 i のキャベツを会社 j に出荷できません。

高橋君は、すべてのキャベツの出荷先を適切に決めることで、すべての会社 j (1 \leq j \leq M) にキャベツを B_j 個以上出荷することができれば「キャベツ名人」の称号を得ることができます。

すぬけ君は、高橋君がどのようにキャベツの出荷先を決めても「キャベツ名人」の称号を得られないように 0 個以上のキャベツを選んで食べることにしました。キャベツが苦手なすぬけ君は、前述の条件のもとで食べるキャベツの個数が 最少 となるように食べるキャベツの組み合わせを選択します。

すぬけ君が食べるキャベツの個数、およびすぬけ君が食べるキャベツの選び方が何通りあるかを 998244353 で割ったあまりの 2 つを出力してください。
ただし、 キャベツの選び方が異なるとは、一方の選び方で食べられたがもう一方の選び方で食べられていないようなキャベツが存在することをいいます。ここで、異なる 2 つのキャベツは 品種が同じでも区別される ことに注意してください。

制約

  • 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 と、すぬけ君が食べるキャベツの選び方が何通りあるかを 998244353 で割ったあまり Y を、この順番に空白区切りで出力せよ。

X Y

入力例 1

3 2
2 2 5
3 4
1 0
1 1
0 1

出力例 1

2 6

高橋君がキャベツ名人になれないようにするために、すぬけ君が食べるキャベツの個数は 2 個です。 また、便宜上 「品種 i の j 番目のキャベツ」を (i,j) のように表したとき、すぬけ君が食べるキャベツの組み合わせとして考えられるものは以下の 6 通りです。

  • (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

すぬけ君がキャベツを 1 個も食べなくても、高橋君がキャベツ名人になることができない場合もあります。
このとき、すぬけ君が食べるキャベツの個数は 0 個であり、すぬけ君が食べるキャベツの組み合わせとして考えられるのは、「どのキャベツも食べない」という 1 通りのみです。

入力例 3

1 3
100
30 30 30
1 1 1

出力例 3

11 892328666

すぬけ君が食べるキャベツの選び方が何通りあるかについては、 998244353 で割ったあまりを出力することに注意してください。

Score : 600 points

Problem Statement

Takahashi, a cabbage farmer, has grown N brands of cabbages, called Brand 1 through Brand N. He has A_i heads of cabbage of Brand i (1 \leq i \leq N). Here, all heads of cabbages are distinguishable.
He has M clients called Company 1 through Company M. Company j (1 \leq j \leq M) has ordered B_j heads of cabbages.
Different companies accept different brands of cabbages. For each pair i, j (1 \leq i \leq N, 1 \leq j \leq M),

  • if c_{i, j} = 1, cabbage of Brand i can be shipped to Company j;
  • if c_{i, j} = 0, cabbage of Brand i cannot be shipped to Company j.

Takahashi will be called a Cabbage Master if he succeeds in deciding where to ship the heads of cabbages so that B_j or more heads of cabbages will be shipped to every company j (1 \leq j \leq M).

Snuke has decided to choose and eat zero or more heads of cabbages so that Takahashi cannot get the title of Cabbage Master, regardless of where to ship his cabbages. He does not like cabbage very much, so he will choose to eat the minimum number of heads of cabbages needed to achieve his objective.

Print the number of heads of cabbages Snuke will eat, and the number of ways, modulo 998244353, for Snuke to choose heads of cabbages to eat. Two ways to choose heads of cabbages are considered different when there is a head of cabbage that is eaten in one way but not in the other. Here, remember that any two heads of cabbages are distinguishable even if they are of the same brand.

Constraints

  • 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
  • For every 1 \leq j \leq M, there exists 1 \leq i \leq N such that c_{i, j} = 1.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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}

Output

Print X, the number of heads of cabbages Snuke will eat, and Y, the number of ways for Snuke to choose heads of cabbages to eat, modulo 998244353, in this order, with a space in between.

X Y

Sample Input 1

3 2
2 2 5
3 4
1 0
1 1
0 1

Sample Output 1

2 6

Snuke will eat two heads of cabbages to prevent Takahashi from becoming a Cabbage Master. There are six such ways to choose heads of cabbages to eat, as shown below, where (i, j) denotes the j-th head of cabbage of Brand 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)

Sample Input 2

1 1
3
4
1

Sample Output 2

0 1

It is possible that Takahashi is unable to become a Cabbage Master even if Snuke eats no cabbage. Then, Snuke will eat zero heads of cabbages, and there is just one way for him to choose heads of cabbages to eat: do not eat anything.

Sample Input 3

1 3
100
30 30 30
1 1 1

Sample Output 3

11 892328666

For the number of ways for Snuke to choose heads of cabbages to eat, be sure to print it modulo 998244353.