#P18243. Sum is One

Sum is One

Sum is One

题目描述

给定一个长度为 NN、仅由 00 和 11 组成的序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N)。

定义一个有 N(N−1)2\frac{N(N-1)}2 个顶点的简单无向图 G=(V,E)G=(V,E):

  • 对每对满足 1≤i<j≤N1\le i<j\le N 的整数 (i,j)(i,j),图中有一个顶点,称为顶点 (i,j)(i,j)。
  • 对每组满足 1≤i<j<k≤N1\le i<j<k\le N 且 Ai+Aj+Ak=1A_i+A_j+A_k=1 的整数 (i,j,k)(i,j,k),在顶点 (i,j)(i,j) 与顶点 (j,k)(j,k) 之间连一条无向边。
  • 其他顶点对之间没有边。

求图 GG 的连通分量个数。

共有 TT 组测试数据,对每组数据分别计算答案。

输入格式

第一行包含一个整数 TT。

接下来依次给出 TT 组测试数据,每组格式如下:

N
A_1 A_2 ... A_N

输出格式

对每组测试数据输出一行,包含一个整数,表示图 GG 的连通分量个数。

数据范围

  • 所有输入值均为整数。
  • 1≤T≤1051\le T\le 10^5。
  • 3≤N≤1063\le N\le 10^6。
  • Ai∈{0,1}A_i\in\{0,1\}。
  • 同一个输入文件中,所有测试数据的 NN 之和不超过 10610^6。

样例

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,2),(2,3),(2,4),(2,5),(3,4),(4,5)\}。
  • {(1,3),(3,5)}\{(1,3),(3,5)\}。
  • {(1,4)}\{(1,4)\}。
  • {(1,5)}\{(1,5)\}。

第二组测试数据中,图中没有边,因此连通分量个数为 1010。