/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
Score: 100 points
Problem Statement
You are given a sequence A = (A_1, A_2, \dots, A_N) of length N consisting of 0s and 1s. Define a simple undirected graph G = (V, E) with \frac{N (N - 1)}{2} vertices as follows:
- For every pair of integers (i, j) satisfying 1 \leq i < j \leq N, (i, j) \in V. This vertex is called vertex (i, j).
- For every triple of integers (i, j, k) satisfying 1 \leq i < j < k \leq N and A_i + A_j + A_k = 1, there is an edge connecting vertex (i, j) and vertex (j, k).
- No other pairs of vertices have edges.
Determine the number of connected components in G.
You are given T test cases. For each test case, compute the answer.
Constraints
- All input values are integers.
- 1 \leq T \leq 10^5
- 3 \leq N \leq 10^6
- A_i is 0 or 1 (1 \leq i \leq N)
- The total sum of N over all test cases in a single input is at most 10^6.
Partial Score
30 points will be awarded for passing the test set satisfying the following constraints:
- 1 \leq T \leq 1000
- 3 \leq N \leq 5000
- The total sum of N over all test cases in a single input is at most 5000.
Input
The input is given in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Here, \text{case}_i represents the i-th test case. Each test case is given in the following format:
N A_1 A_2 \cdots A_N
Output
For each test case, output the answer.
Sample Input 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
Sample Output 1
4 10 13 58
For the first test case, the connected components are as follows:
- \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
For the second test case, the graph has no edges, so the number of connected components is 10.
配点 : 100 点
問題文
0 と 1 からなる長さ N の数列 A = (A_1, A_2, \dots, A_N) が与えられます。\frac{N (N - 1)}{2} 頂点の単純無向グラフ G = (V, E) を以下のように定義します。
- 1 ≤ i < j ≤ N を満たす任意の整数の組 (i, j) に対して、(i, j) \in V である。この頂点を頂点 (i, j) と呼ぶ。
- 1 ≤ i < j < k ≤ N かつ A_i + A_j + A_k = 1 を満たす任意の整数の組 (i, j, k) に対して、頂点 (i, j) と頂点 (j, k) を結ぶ辺が存在する。
- これ以外の頂点の組には辺が存在しない。
G の連結成分の個数を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 入力はすべて整数
- 1 \leq T \leq {10}^5
- 3 \leq N \leq {10}^6
- A_i は 0 または 1 (1 \leq i \leq N)
- 1 つの入力の中のテストケースすべてにわたる N の総和は {10}^6 以下
部分点
以下の制約を満たすデータセットに正解した場合は 30 点が与えられる。
- 1 \leq T \leq 1000
- 3 \leq N \leq 5000
- 1 つの入力の中のテストケースすべてにわたる 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
1 個目のテストケースについて、連結成分は以下の 4 つです。
- \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
2 個目のテストケースについて、グラフに辺は張られないため連結成分の個数は 10 です。