AT_abc215_h [ABC215H] Cabbage Master

[problemUrl]: https://atcoder.jp/contests/abc215/tasks/abc215_h キャベツ農家の高橋君は、品種 $ 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 $ つのキャベツは **品種が同じでも区別される** ことに注意してください。

N/A

N/A

### 制約 - $ 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 $ が成り立つ - 入力はすべて整数 ### Sample Explanation 1 高橋君がキャベツ名人になれないようにするために、すぬけ君が食べるキャベツの個数は $ 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) $ ### Sample Explanation 2 すぬけ君がキャベツを $ 1 $ 個も食べなくても、高橋君がキャベツ名人になることができない場合もあります。 このとき、すぬけ君が食べるキャベツの個数は $ 0 $ 個であり、すぬけ君が食べるキャベツの組み合わせとして考えられるのは、「どのキャベツも食べない」という $ 1 $ 通りのみです。 ### Sample Explanation 3 すぬけ君が食べるキャベツの選び方が何通りあるかについては、 $ 998244353 $ で割ったあまりを出力することに注意してください。