No.1689 Set Cards

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 148
作問者 :

ansain / テスター : 👑

ygussany 👑

Nachia

2 ProblemId : 6495 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2021-09-12 19:19:00

問題文

$N$ 個の集合 $A_{1},$ $A_{2},$ $\dots,$ $A_{N}$ が与えられます。
集合 $A_{i}$ $(1 \leq i \leq N)$ の要素数は $k_{i}$ で、集合 $A_{i}$ は ${C_{i, 1},$ $C_{i, 2},$ $\dots,$ $C_{i, k_{i}}}$ です。
$N$ 個の集合から $1$ 個以上選ぶ $2^{N} - 1$ 通りの選び方のうち、選ばれた集合全ての積集合(共通部分)が空集合であるような選び方は何通りありますか?
ただし、答えは非常に大きくなることがあるので、 $998244353$ で割った余りを出力してください。

入力

 $N$ 
 $k_{1}$   $C_{1, 1}$   $\dots$   $C_{1, k_{1}}$ 
 $k_{2}$   $C_{2, 1}$   $\dots$   $C_{2, k_{2}}$ 
 $⋮$ 
 $k_{N}$   $C_{N, 1}$   $\dots$   $C_{N, k_{N}}$

$1 \leq N \leq 500$
$0 \leq k_{i} \leq 12$
$1 \leq C_{i j} \leq 12$
$C_{i, 1},$ $C_{i, 2},$ $\dots,$ $C_{i, k_{i}}$ は相異なる
入力は全て整数

出力

$2^{N} - 1$ 通りの選び方のうち、選ばれた集合全ての積集合が空集合であるような選び方の数を $998244353$ で割った余りを出力してください。最後に改行してください。

サンプル

サンプル1

入力

出力

$A_{1} = {1, 2}$
$A_{2} = {1, 3}$
$A_{3} = {2, 3}$ です。
$7$ 通りの選び方のうち、 $3$ 個の集合全てを選ぶような選び方しか積集合が空集合になりません。

サンプル2

入力

出力

与えられる集合が空集合であることがあります。

サンプル3

入力

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

出力

301664622

$998244353$ で割った余りを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。