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]$$$:
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])$$$.
8 1 3 2 0 1 3 2 1
71
5 0 0 0 0 0
35
Name |
---|