Для последовательности целых чисел $$$[x_1, x_2, \dots, x_k]$$$ обозначим декомпозицию следующим образом:
Будем обрабатывать последовательность слева направо, поддерживая список ее подпоследовательностей. Когда мы обрабатываем элемент $$$x_i$$$, мы приписываем его в конец первой подпоследовательности в списке, для которой побитовое И последнего ее элемента и $$$x_i$$$ больше $$$0$$$. Если такой подпоследовательности в списке нет, создадим новую подпоследовательность с единственным элементом $$$x_i$$$ и запишем ее в конец списка подпоследовательностей.
Например, рассмотрим декомпозицию последовательности $$$[1, 3, 2, 0, 1, 3, 2, 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])$$$.
8 1 3 2 0 1 3 2 1
71
5 0 0 0 0 0
35
Название |
---|