{"problem":{"name":"Sum is One","description":{"content":"You are given a sequence $A = (A_1, A_2, \\dots, A_N)$ of length $N$ consisting of $0$s and $1$s. Define a simple undirected graph $G = (V, E)$ with $\\frac{N (N - 1)}{2}$ vertices as follows: *   For ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"ttpc2024_1_k"},"statements":[{"statement_type":"Markdown","content":"You are given a sequence $A = (A_1, A_2, \\dots, A_N)$ of length $N$ consisting of $0$s and $1$s. Define a simple undirected graph $G = (V, E)$ with $\\frac{N (N - 1)}{2}$ vertices as follows:\n\n*   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)$.\n*   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)$.\n*   No other pairs of vertices have edges.\n\nDetermine the number of connected components in $G$.\nYou are given $T$ test cases. For each test case, compute the answer.\n\n## Constraints\n\n*   All input values are integers.\n*   $1 \\leq T \\leq 10^5$\n*   $3 \\leq N \\leq 10^6$\n*   $A_i$ is $0$ or $1$ ($1 \\leq i \\leq N$)\n*   The total sum of $N$ over all test cases in a single input is at most $10^6$.\n\n## Input\n\nThe input is given in the following format:\n\n$T$\n$\\text{case}_1$\n$\\text{case}_2$\n$\\vdots$\n$\\text{case}_T$\n\nHere, $\\text{case}_i$ represents the $i$\\-th test case. Each test case is given in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n\n## Partial Score\n\n$30$ points will be awarded for passing the test set satisfying the following constraints:\n\n*   $1 \\leq T \\leq 1000$\n*   $3 \\leq N \\leq 5000$\n*   The total sum of $N$ over all test cases in a single input is at most $5000$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"ttpc2024_1_k","tags":[],"sample_group":[["4\n5\n1 0 0 1 0\n5\n1 1 1 1 1\n12\n0 0 1 1 1 0 0 0 1 0 1 0\n20\n0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 1 1 0 1 1","4\n10\n13\n58\n\nFor the first test case, the connected components are as follows:\n\n*   $\\lbrace (1,2),(2,3),(2,4),(2,5),(3,4),(4,5) \\rbrace$\n*   $\\lbrace (1,3),(3,5) \\rbrace$\n*   $\\lbrace (1,4) \\rbrace$\n*   $\\lbrace (1,5) \\rbrace$\n\nFor the second test case, the graph has no edges, so the number of connected components is $10$."]],"created_at":"2026-03-03 11:01:14"}}