← 返回题目列表

AtCoder · ttpc2024_1_k

K. 总和为一

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

分数: 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.