Decomposition

题意翻译

对于 $n$ 个数 $x_1,x_2,...,x_n$，定义其拆分为： 从 $1$ 到 $n$ 的顺序遍历 $x_1,x_2,...,x_n$。 设当前遍历到 $x_i$： * 如果当前没有序列或者任何一个序列的结尾 $\operatorname{AND}$（按位与）$x_i$ 都为 $0$，那么新开一个序列，新序列中只包含这一个值。 * 否则找到第一个结尾 $\operatorname{AND}\space x_i$ 不为 $0$ 的序列，把 $x_i$ 加在其结尾。 设 $f([x_1,x_2,...,x_n])$ 为拆分得到序列的个数。给出 $a_1,a_2,...,a_n$，求 $\sum_{i=1}^n\sum_{j=i}^nf([a_i,a_{i+1},...,a_j])$。

题目描述

For a sequence of integers $ [x_1, x_2, \dots, x_k] $ , let's define its decomposition as follows: Process the sequence from the first element to the last one, maintaining the list of its subsequences. When you process the element $ x_i $ , append it to the end of the first subsequence in the list such that the bitwise AND of its last element and $ x_i $ is greater than $ 0 $ . If there is no such subsequence in the list, create a new subsequence with only one element $ x_i $ and append it to the end of the list of subsequences. For example, let's analyze the decomposition of the sequence $ [1, 3, 2, 0, 1, 3, 2, 1] $ : - processing element $ 1 $ , the list of subsequences is empty. There is no subsequence to append $ 1 $ to, so we create a new subsequence $ [1] $ ; - processing element $ 3 $ , the list of subsequences is $ [[1]] $ . Since the bitwise AND of $ 3 $ and $ 1 $ is $ 1 $ , the element is appended to the first subsequence; - processing element $ 2 $ , the list of subsequences is $ [[1, 3]] $ . Since the bitwise AND of $ 2 $ and $ 3 $ is $ 2 $ , the element is appended to the first subsequence; - processing element $ 0 $ , the list of subsequences is $ [[1, 3, 2]] $ . There is no subsequence to append $ 0 $ to, so we create a new subsequence $ [0] $ ; - processing element $ 1 $ , the list of subsequences is $ [[1, 3, 2], [0]] $ . There is no subsequence to append $ 1 $ to, so we create a new subsequence $ [1] $ ; - processing element $ 3 $ , the list of subsequences is $ [[1, 3, 2], [0], [1]] $ . Since the bitwise AND of $ 3 $ and $ 2 $ is $ 2 $ , the element is appended to the first subsequence; - processing element $ 2 $ , the list of subsequences is $ [[1, 3, 2, 3], [0], [1]] $ . Since the bitwise AND of $ 2 $ and $ 3 $ is $ 2 $ , the element is appended to the first subsequence; - processing element $ 1 $ , the list of subsequences is $ [[1, 3, 2, 3, 2], [0], [1]] $ . The element $ 1 $ cannot be appended to any of the first two subsequences, but can be appended to the third one. The resulting list of subsequences is $ [[1, 3, 2, 3, 2], [0], [1, 1]] $ . Let $ f([x_1, x_2, \dots, x_k]) $ be the number of subsequences the sequence $ [x_1, x_2, \dots, x_k] $ is decomposed into. Now, for the problem itself. You are given a sequence $ [a_1, a_2, \dots, a_n] $ , where each element is an integer from $ 0 $ to $ 3 $ . Let $ a[i..j] $ be the sequence $ [a_i, a_{i+1}, \dots, a_j] $ . You have to calculate $ \sum \limits_{i=1}^n \sum \limits_{j=i}^n f(a[i..j]) $ .

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ). The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le 3 $ ).

输出格式

Print one integer, which should be equal to $ \sum \limits_{i=1}^n \sum \limits_{j=i}^n f(a[i..j]) $ .

输入输出样例

输入样例 #1

8
1 3 2 0 1 3 2 1

输出样例 #1

71

输入样例 #2

5
0 0 0 0 0

输出样例 #2

35

题意翻译

对于 $n$ 个数 $x_1,x_2,...,x_n$，定义其拆分为： 从 $1$ 到 $n$ 的顺序遍历 $x_1,x_2,...,x_n$。 设当前遍历到 $x_i$： * 如果当前没有序列或者任何一个序列的结尾 $\operatorname{AND}$（按位与）$x_i$ 都为 $0$，那么新开一个序列，新序列中只包含这一个值。 * 否则找到第一个结尾 $\operatorname{AND}\space x_i$ 不为 $0$ 的序列，把 $x_i$ 加在其结尾。 设 $f([x_1,x_2,...,x_n])$ 为拆分得到序列的个数。给出 $a_1,a_2,...,a_n$，求 $\sum_{i=1}^n\sum_{j=i}^nf([a_i,a_{i+1},...,a_j])$。