Submission #18601542

---

Source Code Expand

import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 1_000_000_007

def naive(N):
    S = 'A'
    res = [set() for _ in range(N + 1)]
    se = set([S])
    res[1] = se
    for n in range(2, N + 1):
        newse = set()
        for S in se:
            for i in range(len(S)):
                left = S[:i]
                right = S[i + 1:]
                for x in 'ABC':
                    for y in 'ABC':
                        if x == S[i] or y == S[i] or x == y:
                            continue
                        T = left + x + y + right
                        newse.add(T)
        se = newse
        res[n] = se
    return res

"""import itertools
N = 12
res = naive(N)
for n in range(N):
    print(n, len(res[n]))
for n in range(N):
    for p in itertools.product('ABC',repeat=n):
        p = ''.join(p)
        xor=0
        for x in p:
            xor^='ABC'.index(x) + 1
        if xor==1 and p not in res[n]:
            print(p)"""

@njit((i8[:], ), cache=True)
def main(S):
    S = S + 1
    N = len(S)
    xor = 0
    if np.all(S == S[0]):
        return 1
    prev = np.full(4, -1, np.int64)
    prev[0] = 0
    dp_1 = np.zeros((N + 1, 4), np.int64)
    dp_2 = np.zeros((N + 1, 4), np.int64)
    dp_1[0, 0] = dp_2[0, 0] = 1
    for i in range(1, N + 1):
        x = S[i - 1]
        xor ^= x
        dp_1[i] = dp_1[i - 1]
        j = prev[xor]
        prev[xor] = i
        if j != -1:
            dp_2[i, xor] += dp_1[j, xor]
        for x in range(4):
            if x == xor:
                continue
            dp_2[i, xor] += dp_1[i - 1, x]
            if j != -1:
                dp_2[i, xor] -= dp_1[j, x]
        dp_2[i] %= MOD
        dp_1[i, xor] = dp_2[i, xor]
    ans = dp_2[-1, xor] - dp_2[0, xor]
    return ans % MOD

N = int(readline())
S = np.array(list(readline().rstrip()), np.int64) - ord('A')

print(main(S))

Submission Info

Judge Result