分数: 100 点
问题陈述
给你一个序列 A = (A_1, A_2, \dots, A_N) 长度 N 组成 0和 1定义一个简单的无向图 G = (V, E) 与 \frac{N (N - 1)}{2} 顶点如下:
- 对于每对整数 (i, j) 满意 1 \leq i < j \leq N, (i, j) \in V这个顶点称为顶点 (i, j).
- 对于每一个整数三元组 (i, j, k) 满意 1 \leq i < j < k \leq N 和 A_i + A_j + A_k = 1,有一条边连接顶点 (i, j) 和顶点 (j, k).
- 没有其他顶点对有边。
确定中的连通分量数量 G.
你被给予 T 个测试用例。对于每个测试用例,计算答案。
约束
- 所有输入值均为整数。
- 1 \leq T \leq 10^5
- 3 \leq N \leq 10^6
- A_i is 0 or 1 (1 \leq i \leq N)
- 的总和 N 单个输入中的所有测试用例最多 10^6.
部分分数
30 分将被授予通过满足以下约束的测试集:
- 1 \leq T \leq 1000
- 3 \leq N \leq 5000
- 的总和 N 单个输入中的所有测试用例最多 5000.
输入
输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
在这里, \text{case}_i 代表 i- 第一个测试用例。每个测试用例均按以下格式给出:
N A_1 A_2 \cdots A_N
输出
对于每个测试用例,输出答案。
示例输入 1
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
示例输出 1
4 10 13 58
对于第一个测试用例,连通分量如下:
- \lbrace (1,2),(2,3),(2,4),(2,5),(3,4),(4,5) \rbrace
- \lbrace (1,3),(3,5) \rbrace
- \lbrace (1,4) \rbrace
- \lbrace (1,5) \rbrace
对于第二个测试用例,图没有边,因此连通分量的数量为 10.