Submission #18601542


Source Code Expand

Copy
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

Submission Time
Task E - Shorten ABC
User maspy
Language Python (3.8.2)
Score 800
Code Size 2080 Byte
Status AC
Exec Time 678 ms
Memory 185628 KB

Judge Result

Set Name All Sample
Score / Max Score 800 / 800 0 / 0
Status
AC × 79
AC × 2
Set Name Test Cases
All sample_01.txt, sample_02.txt, testcase_1.txt, testcase_10.txt, testcase_11.txt, testcase_12.txt, testcase_13.txt, testcase_14.txt, testcase_15.txt, testcase_16.txt, testcase_17.txt, testcase_18.txt, testcase_19.txt, testcase_2.txt, testcase_20.txt, testcase_21.txt, testcase_22.txt, testcase_23.txt, testcase_24.txt, testcase_25.txt, testcase_26.txt, testcase_27.txt, testcase_28.txt, testcase_29.txt, testcase_3.txt, testcase_30.txt, testcase_31.txt, testcase_32.txt, testcase_33.txt, testcase_34.txt, testcase_35.txt, testcase_36.txt, testcase_37.txt, testcase_38.txt, testcase_39.txt, testcase_4.txt, testcase_40.txt, testcase_41.txt, testcase_42.txt, testcase_43.txt, testcase_44.txt, testcase_45.txt, testcase_46.txt, testcase_47.txt, testcase_48.txt, testcase_49.txt, testcase_5.txt, testcase_50.txt, testcase_51.txt, testcase_52.txt, testcase_53.txt, testcase_54.txt, testcase_55.txt, testcase_56.txt, testcase_57.txt, testcase_58.txt, testcase_59.txt, testcase_6.txt, testcase_60.txt, testcase_61.txt, testcase_62.txt, testcase_63.txt, testcase_64.txt, testcase_65.txt, testcase_66.txt, testcase_67.txt, testcase_68.txt, testcase_69.txt, testcase_7.txt, testcase_70.txt, testcase_71.txt, testcase_72.txt, testcase_73.txt, testcase_74.txt, testcase_75.txt, testcase_76.txt, testcase_77.txt, testcase_8.txt, testcase_9.txt
Sample sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
sample_01.txt AC 497 ms 105224 KB
sample_02.txt AC 481 ms 105232 KB
testcase_1.txt AC 480 ms 106248 KB
testcase_10.txt AC 487 ms 106300 KB
testcase_11.txt AC 474 ms 105736 KB
testcase_12.txt AC 482 ms 105692 KB
testcase_13.txt AC 479 ms 105580 KB
testcase_14.txt AC 483 ms 105752 KB
testcase_15.txt AC 492 ms 105536 KB
testcase_16.txt AC 480 ms 105500 KB
testcase_17.txt AC 483 ms 105536 KB
testcase_18.txt AC 482 ms 105792 KB
testcase_19.txt AC 483 ms 105592 KB
testcase_2.txt AC 480 ms 106160 KB
testcase_20.txt AC 479 ms 105588 KB
testcase_21.txt AC 483 ms 105240 KB
testcase_22.txt AC 488 ms 105644 KB
testcase_23.txt AC 481 ms 106180 KB
testcase_24.txt AC 481 ms 105536 KB
testcase_25.txt AC 482 ms 105460 KB
testcase_26.txt AC 478 ms 105468 KB
testcase_27.txt AC 483 ms 105560 KB
testcase_28.txt AC 483 ms 105508 KB
testcase_29.txt AC 481 ms 105684 KB
testcase_3.txt AC 488 ms 106252 KB
testcase_30.txt AC 479 ms 105256 KB
testcase_31.txt AC 483 ms 105272 KB
testcase_32.txt AC 493 ms 105536 KB
testcase_33.txt AC 484 ms 105488 KB
testcase_34.txt AC 486 ms 106156 KB
testcase_35.txt AC 477 ms 105504 KB
testcase_36.txt AC 477 ms 106116 KB
testcase_37.txt AC 673 ms 184552 KB
testcase_38.txt AC 665 ms 184828 KB
testcase_39.txt AC 660 ms 184916 KB
testcase_4.txt AC 486 ms 105228 KB
testcase_40.txt AC 660 ms 184884 KB
testcase_41.txt AC 657 ms 185560 KB
testcase_42.txt AC 653 ms 185544 KB
testcase_43.txt AC 657 ms 184792 KB
testcase_44.txt AC 656 ms 184508 KB
testcase_45.txt AC 660 ms 184968 KB
testcase_46.txt AC 663 ms 184964 KB
testcase_47.txt AC 663 ms 184596 KB
testcase_48.txt AC 662 ms 185444 KB
testcase_49.txt AC 658 ms 184828 KB
testcase_5.txt AC 480 ms 105648 KB
testcase_50.txt AC 657 ms 185628 KB
testcase_51.txt AC 655 ms 185524 KB
testcase_52.txt AC 566 ms 144584 KB
testcase_53.txt AC 594 ms 155480 KB
testcase_54.txt AC 579 ms 149772 KB
testcase_55.txt AC 524 ms 125952 KB
testcase_56.txt AC 597 ms 158776 KB
testcase_57.txt AC 557 ms 122312 KB
testcase_58.txt AC 565 ms 122272 KB
testcase_59.txt AC 556 ms 122604 KB
testcase_6.txt AC 490 ms 105688 KB
testcase_60.txt AC 563 ms 123228 KB
testcase_61.txt AC 559 ms 123220 KB
testcase_62.txt AC 559 ms 122496 KB
testcase_63.txt AC 678 ms 185036 KB
testcase_64.txt AC 664 ms 184976 KB
testcase_65.txt AC 657 ms 184600 KB
testcase_66.txt AC 660 ms 185448 KB
testcase_67.txt AC 657 ms 184952 KB
testcase_68.txt AC 657 ms 184980 KB
testcase_69.txt AC 654 ms 184840 KB
testcase_7.txt AC 481 ms 105220 KB
testcase_70.txt AC 659 ms 184964 KB
testcase_71.txt AC 656 ms 184936 KB
testcase_72.txt AC 660 ms 184952 KB
testcase_73.txt AC 659 ms 185488 KB
testcase_74.txt AC 656 ms 184596 KB
testcase_75.txt AC 656 ms 185500 KB
testcase_76.txt AC 656 ms 185560 KB
testcase_77.txt AC 662 ms 184896 KB
testcase_8.txt AC 488 ms 105556 KB
testcase_9.txt AC 484 ms 105652 KB