Sum is One
题目描述
给定一个长度为 N、仅由 0 和 1 组成的序列 A=(A1,A2,…,AN)。
定义一个有 2N(N−1) 个顶点的简单无向图 G=(V,E):
- 对每对满足 1≤i<j≤N 的整数 (i,j),图中有一个顶点,称为顶点 (i,j)。
- 对每组满足 1≤i<j<k≤N 且 Ai+Aj+Ak=1 的整数 (i,j,k),在顶点 (i,j) 与顶点 (j,k) 之间连一条无向边。
- 其他顶点对之间没有边。
求图 G 的连通分量个数。
共有 T 组测试数据,对每组数据分别计算答案。
输入格式
第一行包含一个整数 T。
接下来依次给出 T 组测试数据,每组格式如下:
N
A_1 A_2 ... A_N
输出格式
对每组测试数据输出一行,包含一个整数,表示图 G 的连通分量个数。
数据范围
- 所有输入值均为整数。
- 1≤T≤105。
- 3≤N≤106。
- Ai∈{0,1}。
- 同一个输入文件中,所有测试数据的 N 之和不超过 106。
样例
4
5
1 0 0 1 0
5
1 1 1 1 1
12
0 0 1 1 1 0 0 0 1 0 1 0
20
0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 1 1 0 1 1
4
10
13
58
样例说明
第一组测试数据中,四个连通分量的顶点集合分别为:
- {(1,2),(2,3),(2,4),(2,5),(3,4),(4,5)}。
- {(1,3),(3,5)}。
- {(1,4)}。
- {(1,5)}。
第二组测试数据中,图中没有边,因此连通分量个数为 10。