← 返回题目列表

Codeforces · 1766/E

E. 分解

中文机器翻译题面 查看原题

对于整数序列 $$$[x_1, x_2, \dots, x_k]$$$,我们将其分解定义如下:

处理从第一个元素到最后一个元素的序列,维护其子序列的列表。处理元素 $$$x_i$$$ 时,将其附加到列表中第一个子序列的末尾,使其最后一个元素与 $$$x_i$$$ 的按位 AND 大于 $$$0$$$。如果列表中没有这样的子序列,则创建一个只有一个元素 $$$x_i$$$ 的新子序列,并将其附加到子序列列表的末尾。

例如我们来分析序列$$$[1, 3, 2, 0, 1, 3, 2, 1]$$$的分解:

- 处理元素$$$1$$$,子序列列表为空。没有子序列可以追加$$$1$$$,因此我们创建一个新的子序列$$$[1]$$$;
- 处理元素$$$3$$$,子序列列表为$$$[[1]]$$$。由于$$$3$$$ 和$$$1$$$ 的按位与为$$$1$$$,因此该元素被追加到第一个子序列中;
- 处理元素$$$2$$$,子序列列表为$$$[[1, 3]]$$$。由于$$$2$$$ 和$$$3$$$ 的按位与为$$$2$$$,因此该元素被追加到第一个子序列;
- 处理元素$$$0$$$,子序列列表为$$$[[1, 3, 2]]$$$。没有子序列可以追加$$$0$$$,因此我们创建一个新的子序列$$$[0]$$$;
- 处理元素$$$1$$$,子序列列表为$$$[[1, 3, 2], [0]]$$$。没有子序列可以追加$$$1$$$,因此我们创建一个新的子序列$$$[1]$$$;
- 处理元素$$$3$$$,子序列列表为$$$[[1, 3, 2], [0], [1]]$$$。由于$$$3$$$ 和$$$2$$$ 的按位与为$$$2$$$,因此该元素被追加到第一个子序列;
- 处理元素$$$2$$$,子序列列表为$$$[[1, 3, 2, 3], [0], [1]]$$$。由于$$$2$$$ 和$$$3$$$ 的按位与为$$$2$$$,因此该元素被追加到第一个子序列;
- 处理元素$$$1$$$,子序列列表为$$$[[1, 3, 2, 3, 2], [0], [1]]$$$。元素 $$$1$$$ 不能附加到前两个子序列中的任何一个,但可以附加到第三个子序列。

子序列的结果列表为 $$$[[1, 3, 2, 3, 2], [0], [1, 1]]$$$。

设 $$$f([x_1, x_2, \dots, x_k])$$$ 为序列 $$$[x_1, x_2, \dots, x_k]$$$ 分解为的子序列数。

现在,针对问题本身。

给定一个序列 $$$[a_1, a_2, \dots, a_n]$$$,其中每个元素都是从 $$$0$$$ 到 $$$3$$$ 的整数。设 $$$a[i..j]$$$ 为序列 $$$[a_i, a_{i+1}, \dots, a_j]$$$。您必须计算 $$$\sum \limits_{i=1}^n \sum \limits_{j=i}^n f(a[i..j])$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 3$$$)。

输出

打印一个整数,该整数应等于 $$$\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