← 返回题目列表

AtCoder · past18_e

E. 常用零件

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

问题陈述

有 N 整数组: S_1, S_2, \dots, S_N.
S_i 包含 C_i 整数, A_{i, 1}, \dots, A_{i, C_i},按升序排列。
在选择两个或多个集合的方式中,有多少个集合满足以下条件?

  • 所选集合的交集仅包含奇数。

这里,所选集合的交集是由所有所选集合中包含的整数组成的集合。

约束

  • 2 \leq N \leq 10
  • 1 \leq C_i \leq 10
  • 1 \leq A_{i,1} \lt A_{i,2} \lt \dots \lt A_{i,C_i} \leq 100
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
C_1 A_{1,1} A_{1,2} \dots A_{1,C_1}
C_2 A_{2,1} A_{2,2} \dots A_{2,C_2}
\vdots
C_N A_{N,1} A_{N,2} \dots A_{N,C_N}

输出

打印答案。


示例输入 1

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

示例输出 1

3

我们枚举集合的可能选择、它们的交集以及它们是否满足条件:

  • 的交集 S_1 和 S_2 is \lbrace 1, 5 \rbrace,满足条件。
  • 的交集 S_1 和 S_3 is \lbrace 2 \rbrace,不满足条件。
  • 的交集 S_2 和 S_3 is \lbrace 3 \rbrace,满足条件。
  • 的交集 S_1, S_2,和 S_3 is \lbrace \rbrace (空集),满足条件。

请注意,即使交集是空集,条件也满足。


示例输入 2

5
6 4 5 6 9 10 17
5 1 7 9 13 20
6 2 5 8 15 16 20
6 2 5 6 7 16 19
1 3

示例输出 2

23