AtCoder Regular Contest++ 216
统计 2 的幂AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)You are given a sequence of non-negative integers $A = (A_1, A_2, \ldots, A_N)$ of length $N$.
给定一个长度为 $N$ 的非负整数序列 $A = (A_1, A_2, \ldots, A_N)$。AI (CI翻译)
Find the number of pairs of integers $(l, r)\ (1 \leq l \leq r \leq N)$ such that $2^{A_l} + 2^{A_{l+1}} + \dots + 2^{A_r}$ is a power of $2$. Here, a power of $2$ is a number expressible as $2^k$ for some non-negative integer $k$.
请求出满足以下条件的整数对 $(l, r)\ (1 \leq l \leq r \leq N)$ 的数量：$2^{A_l} + 2^{A_{l+1}} + \dots + 2^{A_r}$ 是 $2$ 的幂。其中，$2$ 的幂是指可以表示为 $2^k$（其中 $k$ 为非负整数）的数。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$1 \leq N \leq 2 \times 10^5$$0 \leq A_i \leq 2 \times 10^5$- All input values are integers.
$1 \leq N \leq 2 \times 10^5$$0 \leq A_i \leq 2 \times 10^5$- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
N
A_1 A_2 \ldots A_NN
A_1 A_2 \ldots A_NOutput
输出格式
AI (CI翻译)Print the answer.
输出答案。AI (CI翻译)
样例
Input #1
4
0 1 0 2
Output #1
6
The pairs $(l, r)$ satisfying the condition are $(1,1), (1,3), (1,4), (2,2), (3,3), (4,4)$, totaling six pairs.
Input #2
4
100 100 100 100
Output #2
8
Input #3
10
3 2 2 3 2 4 1 1 0 0
Output #3
19
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。