Decomposition (Codeforces 1766E)
Tags: DP, divide and conquer

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])$$$.

Input: 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$$$).

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


Sample Inputs:
8
1 3 2 0 1 3 2 1

5
0 0 0 0 0

Sample Outputs:
71

35

Solution (Python):
def nextstate(q, x):
    i = 0
    for i in range(len(q)):
        if q[i] & x > 0:
            return q[:i] + (x,) + q[i + 1:]
    return q + (x,)
qs = [()]
trans = []
ptr = 0
while ptr < len(qs):
    q = qs[ptr]
    tb = []
    for x in range(1, 4):
        qn = nextstate(q, x)
        if qn not in qs:
            qs.append(qn)
        tb.append(qs.index(qn))
    trans.append(tb)
    ptr += 1
n = int(input())
a = [int(x) for x in input().split(' ')]
cnt = [0] * len(qs)
cnt[0] = 1
ans = 0
for (i, ai) in enumerate(a):
    cnt2 = [0] * len(qs)
    cnt2[0] = 1
    if ai == 0:
        for j in range(len(qs)):
            cnt2[j] += cnt[j]
        ans += (i + 1) * (n - i)
    else:
        for j in range(len(qs)):
            qn = trans[j][ai - 1]
            cnt2[qn] += cnt[j]
    for j in range(len(qs)):
        ans += cnt2[j] * len(qs[j])
    cnt = cnt2
print(ans)

Solution (Python):
def nextstate(q, x):
    i = 0
    for i in range(len(q)):
        if q[i] & x > 0:
            return q[:i] + (x,) + q[i + 1:]
    return q + (x,)
qs = [()]
trans = []
ptr = 0
while ptr < len(qs):
    q = qs[ptr]
    tb = []
    for x in range(1, 4):
        qn = nextstate(q, x)
        if qn not in qs:
            qs.append(qn)
        tb.append(qs.index(qn))
    trans.append(tb)
    ptr += 1
n = int(input())
a = [int(x) for x in input().split(' ')]
cnt = [0] * len(qs)
cnt[0] = 1
ans = 0
for (i, ai) in enumerate(a):
    cnt2 = [0] * len(qs)
    cnt2[0] = 1
    if ai == 0:
        for j in range(len(qs)):
            cnt2[j] += cnt[j]
        ans += (i + 1) * (n - i)
    else:
        for j in range(len(qs)):
            qn = trans[j][ai - 1]
            cnt2[qn] += cnt[j]
    for j in range(len(qs)):
        ans += cnt2[j] * len(qs[j])
    cnt = cnt2
print(ans)

Solution (Python):
import os, sys
from io import BytesIO, IOBase
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop
from functools import lru_cache
from itertools import accumulate
import math
import sys
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ii = lambda : int(input())
mii = lambda : map(int, input().split())
fii = lambda : map(float, input().split())
lmii = lambda : list(map(int, input().split()))
i2c = lambda n: chr(ord('a') + n)
c2i = lambda c: ord(c) - ord('a')
mod = 998244353

def solve():
    n = ii()
    l = lmii()
    res = 0
    for i in range(n):
        if l[i] == 0:
            res += (i + 1) * (n - i)
    m0 = 0
    cur0 = 0
    for (i, k) in enumerate(l):
        if k == 0:
            cur0 += 1
        else:
            m0 += cur0 * (cur0 + 1) // 2
            cur0 = 0
    m0 += cur0 * (cur0 + 1) // 2
    (m1, m3) = (0, 0)
    tl = []
    tle = []
    temp = []
    last = 0
    for (i, k) in enumerate(l):
        if k == 0:
            continue
        if not tle:
            tle.append(k)
            temp.append(i)
        elif k != tle[-1]:
            temp.append(last)
            tl.append(temp)
            temp = [i]
            tle.append(k)
        last = i
    temp.append(last)
    tl.append(temp)
    left = 0
    (l12, l21) = ([], [])
    for i in range(len(tle) - 1):
        if tle[i] + tle[i + 1] == 3:
            if tle[i] == 1:
                l12.append([left, tl[i][1], tl[i + 1][0]])
            else:
                l21.append([left, tl[i][1], tl[i + 1][0]])
            v = tl[i + 1][0] - tl[i][1] - 1
            m1 -= v * (v + 1) // 2
            u = tl[i + 1][0] - left
            left = tl[i][1] + 1
            m1 += u * (u + 1) // 2
    u = n - left
    m1 += u * (u + 1) // 2
    (l312, l321) = ([], [])
    for i in range(len(tle) - 2):
        if tle[i] == 3 and tle[i + 1] == 1 and (tle[i + 2] == 2):
            l312.append(tl[i + 2][0])
        if tle[i] == 3 and tle[i + 1] == 2 and (tle[i + 2] == 1):
            l321.append(tl[i + 2][0])
    for (x, y, z) in l12:
        i = bisect_left(l321, z)
        if i == len(l321):
            continue
        m3 += (y - x + 1) * (n - l321[i])
    for (x, y, z) in l21:
        i = bisect_left(l312, z)
        if i == len(l312):
            continue
        m3 += (y - x + 1) * (n - l312[i])
    res += n * (n + 1) - m0 - m1 + m3
    print(res)
for _ in range(1):
    solve()