Problem:


Score : 700 points

Problem Statement

You are given a string S consisting of a,b and c. Find the number of strings that can be possibly obtained by repeatedly performing the following operation zero or more times, modulo 998244353:

Choose an integer i such that 1\leq i\leq |S|-1 and the i-th and (i+1)-th characters in S are different. Replace each of the i-th and (i+1)-th characters in S with the character that differs from both of them (among a, b and c).

Constraints

2 \leq |S| \leq 2 × 10^5

S consists of a, b and c.

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of strings that can be possibly obtained by repeatedly performing the operation, modulo 998244353.

Sample Input 1

abc

Sample Output 1

3

abc, aaa and ccc can be obtained.

Sample Input 2

abbac

Sample Output 2

65

Sample Input 3

babacabac

Sample Output 3

6310

Sample Input 4

ababacbcacbacacbcbbcbbacbaccacbacbacba

Sample Output 4

148010497



Sample input:
abc


Sample output:
3

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

import numpy as np

MOD = 998244353

S = input().rstrip()

arr = np.array(list(S.replace('a','0').replace('b','1').replace('c','2')),dtype=np.int32)

def solve_naive(S):
    se = set([S])
    q = [S]
    while q:
        S = q.pop()
        for i in range(len(S)-1):
            x,y = S[i:i+2]
            if x == y:
                continue
            for t in 'abc':
                if t != x and t != y:
                    T = S[:i] + t+t + S[i+2:]
                    if T not in se:
                        q.append(T)
                        se.add(T)
    return len(se)

LS = len(S)
if LS < 6:
    answer = solve_naive(S)
    print(answer)
    exit()

# 適当な必要条件のもと全部作れる
# mod 3不変量
answer = pow(3,LS-1,MOD)
# 同一値の連続が存在しないものを間引く
if LS%3 == 0:
    x,y = (3+MOD)//2,0
    for _ in range(LS//3):
        x,y = 4*x+4*y,2*x+6*y
        x %= MOD
        y %= MOD
    if arr.sum()%3 == 0:
        answer -= x
    else:
        answer -= y
else:
    answer -= pow(2,LS-1,MOD)
# 初手に完成しているやつは使って良い
if (arr[:-1] != arr[1:]).all():
    answer += 1

answer %= MOD
print(answer)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
MOD = 998244353

import sys

S=input()

if len(S)==2:
    if S[0]==S[1]:
        print(1)
    else:
        print(2)
    sys.exit()    

flag1=0
flag2=0
for i in range(len(S)):
    if S[i] != S[0]:
        flag1 = 1
        break

for i in range(len(S)-1):
    if S[i+1] == S[i]:
        flag2 = 1
        break

c=0
for i in range(len(S)):
    if S[i]=='a':
        c+=1
    elif S[i]=='b':
        c+=2

if flag1==0:
    print(1)
    sys.exit()    
L = len(S)
dp = [[[0 for i in range(3)] for j in range(3)] for k in range(L+1)]
for a in range(3):
    dp[0][a][a]=1
for i in range(1,L):
    for p in range(3):
        for a in range(3):
#            print(i,p,a)
            dp[i][(p+a+1)%3][(a+1)%3] += dp[i-1][p][a] 
            dp[i][(p+a+1)%3][(a+1)%3] %= MOD 
            dp[i][(p+a+2)%3][(a+2)%3] += dp[i-1][p][a]
            dp[i][(p+a+2)%3][(a+2)%3] %= MOD
#print(dp)
print((pow(3,(len(S)-1),MOD) - dp[L-1][c%3][0] - dp[L-1][c%3][1] - dp[L-1][c%3][2] + (1-flag2))%MOD)

Submission status: Wrong Answer

Solution code:
s = list(input())

n = len(s)

a = [0] * n

MOD = 998244353

for i in range(n):
    a[i] = ord(s[i]) - ord('a')

if max(a) == min(a):
    print(1)
    exit()
elif n == 3:
    def solver(m):
        x = m // 100
        y = ( m % 100 ) // 10
        z = m % 10
        if x != y:
            c = (3 - x - y) % 3
            temp = c * 110 + z
            if temp not in ans:
                ans.add(temp)
                solver(temp)
        if y != z:
            c = (3 - y - z) % 3
            temp = x * 100 + c * 11
            if temp not in ans:
                ans.add(temp)
                solver(temp)

    t = a[0] * 100 + a[1] * 10 + a[2]
    ans = set()
    ans.add(t)
    solver(t)
    print(len(ans))
    exit()
elif n == 2:
    print(2)
    exit()

dp = [[0,0,0] for _ in range(3)]

dp[0][0] = 1
dp[1][1] = 1
dp[2][2] = 1

for i in range(n-1):
    T = [[0,0,0] for _ in range(3)]
    T[0][0] = dp[1][0] + dp[2][0]
    T[0][1] = dp[1][1] + dp[2][1]
    T[0][2] = dp[1][2] + dp[2][2]
    T[1][0] = dp[0][2] + dp[2][2]
    T[1][1] = dp[0][0] + dp[2][0]
    T[1][2] = dp[0][1] + dp[2][1]
    T[2][0] = dp[0][1] + dp[1][1]
    T[2][1] = dp[0][2] + dp[1][2]
    T[2][2] = dp[0][0] + dp[1][0]
    dp, T = T, dp

m = sum(a) % 3

ans = 3 ** (n-1) - (dp[0][m] + dp[1][m] + dp[2][m])

check = 1
for i in range(n-1):
    if a[i] == a[i+1]:
        check = 0
        break

ans += check

print(dp, 2 ** (n-1))

print(ans % MOD)

Submission status: Wrong Answer

Solution code:
def modprod(n, d, mod):
    """
    n^d % mod
    :param n:
    :param d:
    :param mod:
    :return:
    """
    ans = 1
    for i in range(d):
        ans *= n
        ans %= mod
    return ans


def F():
    S = input()
    mod = 998244353
    S = list(map(int, S.replace('a', '0').replace('b', '1').replace('c', '2')))
    zorome = True
    bara = False
    for i in range(len(S)-1):
        if S[i+1] == S[i]:
            bara = True
        else:
            zorome = False

    if zorome:
        print(1)
    else:
        ans = (modprod(3, len(S)-1, mod) - modprod(2, len(S)-1, mod)) % mod
        if bara:
            print(ans)
        else:
            print(ans+1)


if __name__ == '__main__':
    F()

Submission status: Wrong Answer

Solution code:
def solve(s):
    if len(s) == 2:
        return 1 if s[0] == s[1] else 2
    elif len(s) == 3:
        if s[0] == s[1] == s[2]:
            return 1
        elif s[0] == s[1] or s[1] == s[2]:
            return 6
        elif s[0] == s[2]:
            return 7
        else:
            return 3
    dp = [[[0] * 3 for _ in range(3)] for _ in range(2)]
    dp[0][0][0] = 1
    dp[0][1][1] = 1
    dp[0][2][2] = 1
    MOD = 998244353
    for _ in range(len(s) - 1):
        ndp = [[[0] * 3 for _ in range(3)] for _ in range(2)]
        ndp[0][0][0] = (dp[0][1][0] + dp[0][2][0]) % MOD
        ndp[0][0][1] = (dp[0][1][1] + dp[0][2][1]) % MOD
        ndp[0][0][2] = (dp[0][1][2] + dp[0][2][2]) % MOD
        ndp[0][1][0] = (dp[0][0][2] + dp[0][2][2]) % MOD
        ndp[0][1][1] = (dp[0][0][0] + dp[0][2][0]) % MOD
        ndp[0][1][2] = (dp[0][0][1] + dp[0][2][1]) % MOD
        ndp[0][2][0] = (dp[0][0][1] + dp[0][1][1]) % MOD
        ndp[0][2][1] = (dp[0][0][2] + dp[0][1][2]) % MOD
        ndp[0][2][2] = (dp[0][0][0] + dp[0][1][0]) % MOD
        ndp[1][0][0] = (dp[0][0][0] + dp[1][0][0] + dp[1][1][0] + dp[1][2][0]) % MOD
        ndp[1][0][1] = (dp[0][0][1] + dp[1][0][1] + dp[1][1][1] + dp[1][2][1]) % MOD
        ndp[1][0][2] = (dp[0][0][2] + dp[1][0][2] + dp[1][1][2] + dp[1][2][2]) % MOD
        ndp[1][1][0] = (dp[0][1][2] + dp[1][0][2] + dp[1][1][2] + dp[1][2][2]) % MOD
        ndp[1][1][1] = (dp[0][1][0] + dp[1][0][0] + dp[1][1][0] + dp[1][2][0]) % MOD
        ndp[1][1][2] = (dp[0][1][1] + dp[1][0][1] + dp[1][1][1] + dp[1][2][1]) % MOD
        ndp[1][2][0] = (dp[0][2][1] + dp[1][0][1] + dp[1][1][1] + dp[1][2][1]) % MOD
        ndp[1][2][1] = (dp[0][2][2] + dp[1][0][2] + dp[1][1][2] + dp[1][2][2]) % MOD
        ndp[1][2][2] = (dp[0][2][0] + dp[1][0][0] + dp[1][1][0] + dp[1][2][0]) % MOD
        dp = ndp
    return (sum(dp[1][x][sum(map(ord, s)) % 3] for x in range(3)) + all(a != b for a, b in zip(s, s[1:]))) % MOD


s = input()
print(solve(s))

Submission status: Wrong Answer

Solution code:
def solve(s):
    if len(s) == 2:
        return 1 if s[0] == s[1] else 2
    elif len(s) == 3:
        if s[0] == s[1] == s[2]:
            return 1
        elif s[0] == s[1] or s[1] == s[2]:
            return 6
        elif s[0] == s[2]:
            return 7
        else:
            return 3
    dp = [[[0] * 3 for _ in range(3)] for _ in range(2)]
    dp[0][0][0] = 1
    dp[0][1][1] = 1
    dp[0][2][2] = 1
    MOD = 998244353
    for _ in range(len(s) - 1):
        ndp = [[[0] * 3 for _ in range(3)] for _ in range(2)]
        ndp[0][0][0] = (dp[0][1][0] + dp[0][2][0]) % MOD
        ndp[0][0][1] = (dp[0][1][1] + dp[0][2][1]) % MOD
        ndp[0][0][2] = (dp[0][1][2] + dp[0][2][2]) % MOD
        ndp[0][1][0] = (dp[0][0][2] + dp[0][2][2]) % MOD
        ndp[0][1][1] = (dp[0][0][0] + dp[0][2][0]) % MOD
        ndp[0][1][2] = (dp[0][0][1] + dp[0][2][1]) % MOD
        ndp[0][2][0] = (dp[0][0][1] + dp[0][1][1]) % MOD
        ndp[0][2][1] = (dp[0][0][2] + dp[0][1][2]) % MOD
        ndp[0][2][2] = (dp[0][0][0] + dp[0][1][0]) % MOD
        ndp[1][0][0] = (dp[0][0][0] + dp[1][0][0] + dp[1][1][0] + dp[1][2][0]) % MOD
        ndp[1][0][1] = (dp[0][0][1] + dp[1][0][1] + dp[1][1][1] + dp[1][2][1]) % MOD
        ndp[1][0][2] = (dp[0][0][2] + dp[1][0][2] + dp[1][1][2] + dp[1][2][2]) % MOD
        ndp[1][1][0] = (dp[0][1][2] + dp[1][0][2] + dp[1][1][2] + dp[1][2][2]) % MOD
        ndp[1][1][1] = (dp[0][1][0] + dp[1][0][0] + dp[1][1][0] + dp[1][2][0]) % MOD
        ndp[1][1][2] = (dp[0][1][1] + dp[1][0][1] + dp[1][1][1] + dp[1][2][1]) % MOD
        ndp[1][2][0] = (dp[0][2][1] + dp[1][0][1] + dp[1][1][1] + dp[1][2][1]) % MOD
        ndp[1][2][1] = (dp[0][2][2] + dp[1][0][2] + dp[1][1][2] + dp[1][2][2]) % MOD
        ndp[1][2][2] = (dp[0][2][0] + dp[1][0][0] + dp[1][1][0] + dp[1][2][0]) % MOD
        dp = ndp
    return sum(dp[1][x][sum(map(ord, s)) % 3] for x in range(3)) + all(a != b for a, b in zip(s, s[1:]))


s = input()
print(solve(s))

Submission status: Wrong Answer

Solution code:
import numpy as np


def solve(s):
    if len(s) == 2:
        return 1 if s[0] == s[1] else 2
    elif len(s) == 3:
        if s[0] == s[1] == s[2]:
            return 1
        elif s[0] == s[1] or s[1] == s[2]:
            return 6
        elif s[0] == s[2]:
            return 7
        else:
            return 3
    dp = [[[0] * 3 for _ in range(3)] for _ in range(2)]
    dp[0][0][0] = 1
    dp[0][1][1] = 1
    dp[0][2][2] = 1
    MOD = 998244353
    for _ in range(len(s) - 1):
        ndp = [[[0] * 3 for _ in range(3)] for _ in range(2)]
        ndp[0][0][0] = (dp[0][1][0] + dp[0][2][0]) % MOD
        ndp[0][0][1] = (dp[0][1][1] + dp[0][2][1]) % MOD
        ndp[0][0][2] = (dp[0][1][2] + dp[0][2][2]) % MOD
        ndp[0][1][0] = (dp[0][0][2] + dp[0][2][2]) % MOD
        ndp[0][1][1] = (dp[0][0][0] + dp[0][2][0]) % MOD
        ndp[0][1][2] = (dp[0][0][1] + dp[0][2][1]) % MOD
        ndp[0][2][0] = (dp[0][0][1] + dp[0][1][1]) % MOD
        ndp[0][2][1] = (dp[0][0][2] + dp[0][1][2]) % MOD
        ndp[0][2][2] = (dp[0][0][0] + dp[0][1][0]) % MOD
        ndp[1][0][0] = (dp[0][0][0] + dp[1][0][0] + dp[1][1][0] + dp[1][2][0]) % MOD
        ndp[1][0][1] = (dp[0][0][1] + dp[1][0][1] + dp[1][1][1] + dp[1][2][1]) % MOD
        ndp[1][0][2] = (dp[0][0][2] + dp[1][0][2] + dp[1][1][2] + dp[1][2][2]) % MOD
        ndp[1][1][0] = (dp[0][1][2] + dp[1][0][2] + dp[1][1][2] + dp[1][2][2]) % MOD
        ndp[1][1][1] = (dp[0][1][0] + dp[1][0][0] + dp[1][1][0] + dp[1][2][0]) % MOD
        ndp[1][1][2] = (dp[0][1][1] + dp[1][0][1] + dp[1][1][1] + dp[1][2][1]) % MOD
        ndp[1][2][0] = (dp[0][2][1] + dp[1][0][1] + dp[1][1][1] + dp[1][2][1]) % MOD
        ndp[1][2][1] = (dp[0][2][2] + dp[1][0][2] + dp[1][1][2] + dp[1][2][2]) % MOD
        ndp[1][2][2] = (dp[0][2][0] + dp[1][0][0] + dp[1][1][0] + dp[1][2][0]) % MOD
        dp = ndp
    t = list(map(ord, s))
    return sum(dp[1][x][sum(t) % 3] for x in range(3)) + np.diff(t).all()


s = input()
print(solve(s))

Submission status: Wrong Answer

Solution code:
def main():
    a = raw_input().strip()
    l = len(a)
    if l < 6:
        s = set()
        s.add(a)
        q = [a]
        oa = ord('a')
        while q:
            a = q.pop()
            for i in xrange(l - 1):
                if a[i] != a[i+1]:
                    t = chr(oa + 3 - (ord(a[i]) - oa) - (ord(a[i+1]) - oa))
                    na = a[:i] + t * 2 + a[i+2:]
                    if na not in s:
                        s.add(na)
                        q.append(na)
        print len(s)
        return
    t = a[0] * l
    if t == a:
        print 1
        return
    x = 0
    for c in a:
        if c == 'b':
            x += 1
        elif c == 'c':
            x += 2
    ans = 0
    if all(a[i] != a[i+1] for i in xrange(l - 1)):
        ans += 1
    mod = 998244353
    dp = (1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0)
    for i in xrange(l - 1):
        s = (dp[-1] + dp[-2] + dp[-3]) % mod
        dp = ((dp[3]+dp[6])%mod,(dp[4]+dp[7])%mod,(dp[5]+dp[8])%mod,(dp[2]+dp[8])%mod,(dp[0]+dp[6])%mod,(dp[1]+dp[7])%mod,(dp[1]+dp[4])%mod,(dp[2]+dp[5])%mod,(dp[0]+dp[3])%mod,(dp[0]+dp[5]+dp[7]+s)%mod,(dp[1]+dp[4]+dp[8]+s)%mod,(dp[2]+dp[3]+dp[6]+s)%mod)
    print (ans + dp[9+x%3]) % mod
main()

Submission status: Wrong Answer

Solution code:
def main():
    a = raw_input().strip()
    l = len(a)
    if l < 6:
        s = set()
        s.add(a)
        q = [a]
        oa = ord('a')
        while q:
            a = q.pop()
            for i in xrange(l - 1):
                if a[i] != a[i+1]:
                    t = chr(oa + 3 - (ord(a[i]) - oa) - (ord(a[i+1]) - oa))
                    na = a[:i] + t * 2 + a[i+2:]
                    if na not in s:
                        s.add(na)
                        q.append(na)
        print len(s)
        return
    t = a[0] * l
    if t == a:
        print 1
        return
    ans = 0
    if all(a[i] != a[i+1] for i in xrange(l - 1)):
        ans += 1
    mod = 998244353
    dp = (1, 1, 1, 0)
    for i in xrange(l - 1):
        s = (dp[0] + dp[1] + dp[2]) % mod
        dp = ((dp[1] + dp[2]) % mod, (dp[0] + dp[2]) % mod, (dp[0] + dp[1]) % mod, (s + dp[3] * 3) % mod)
    print (ans + dp[-1] / 3) % mod
main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

def main():
    md = 998244353
    s = input()
    n = len(s)
    if s.count(s[0]) == n:
        print(1)
        exit()
    if n == 2:
        print(2)
        exit()
    if n == 3:
        if s[0] == s[-1]:
            print(7)
        elif s[0] == s[1] or s[1] == s[2]:
            print(6)
        else:
            print(3)
        exit()
    ord0 = ord("a")
    a = [ord(c) - ord0 for c in s]
    r = sum(a) % 3
    dp = [[[[0] * 3 for _ in range(2)] for _ in range(3)] for _ in range(n)]
    for m in range(3):
        dp[0][m][0][m] = 1
    # print(a)
    # print(dp)
    for i in range(n - 1):
        for j in range(3):
            for k in range(2):
                for m in range(3):
                    pre = dp[i][j][k][m]  # iけた j余り k連続有無 m前の位
                    for nm in range(3):
                        nj = (j + nm) % 3
                        if nm == m:
                            dp[i + 1][nj][1][nm] = (dp[i + 1][nj][1][nm] + pre) % md
                        else:
                            dp[i + 1][nj][k][nm] = (dp[i + 1][nj][k][nm] + pre) % md
    d = 1
    for c0, c1 in zip(s, s[1:]):
        if c0 == c1:
            d = 0
            break
    print((sum(dp[n - 1][r][1]) + d) % md)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
S=input()
N=len(S)
if N==3:
    if S[0]==S[1]:
        if S[1]==S[2]:
            print(1)
        else:
            print(6)
    else:
        if S[0]==S[2]:
            print(7)
        elif S[1]==S[2]:
            print(6)
        else:
            print(3)
    sys.exit()
mod=998244353
M=0
for s in S:
    if s=='b':
        M+=1
    elif s=='c':
        M+=2
    M%=3
dd=defaultdict(int)
for i in range(3):
    dd[(0,i,i)]=1
for k in range(2,N+1):
    nd=defaultdict(int)
    for p,n in dd.items():
        con,moji,m=p
        #print(con,moji,m)
        if con==0:
            for k in range(3):
                if moji==k:
                    nd[(1, k, (m + k) % 3)] += n
                    nd[(1, k, (m + k) % 3)] %=mod
                else:
                    nd[(0,k,(m+k)%3)]+=n
                    nd[(0, k, (m+k) % 3)] %=mod
        else:
            for k in range(3):
                nd[(1, k, (m + k) % 3)] += n
                nd[(1, k, (m + k) % 3)] %=mod
    #print(nd)
    dd=nd
flag=1
for i in range(N-1):
    if S[i]==S[i+1]:
        flag=0
ans=flag
for p, n in dd.items():
    con, moji, m = p
    if m==M and con==1:
        ans+=n
        ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())

n = len(s)

a = [0] * n

MOD = 998244353

for i in range(n):
    a[i] = ord(s[i]) - ord('a')

if max(a) == min(a):
    print(1)
    exit()
elif n == 3:
    def solver(m):
        x = m // 100
        y = ( m % 100 ) // 10
        z = m % 10
        if x != y:
            c = (3 - x - y) % 3
            temp = c * 110 + z
            if temp not in ans:
                ans.add(temp)
                solver(temp)
        if y != z:
            c = (3 - y - z) % 3
            temp = x * 100 + c * 11
            if temp not in ans:
                ans.add(temp)
                solver(temp)

    t = a[0] * 100 + a[1] * 10 + a[2]
    ans = set()
    ans.add(t)
    solver(t)
    print(len(ans))
    exit()
elif n == 2:
    print(2)
    exit()

dp = [[0,0,0] for _ in range(3)]

dp[0][0] = 1
dp[1][1] = 1
dp[2][2] = 1

for i in range(n-1):
    T = [[0,0,0] for _ in range(3)]
    T[0][0] = dp[1][0] + dp[2][0]
    T[0][1] = dp[1][1] + dp[2][1]
    T[0][2] = dp[1][2] + dp[2][2]
    T[1][0] = dp[0][2] + dp[2][2]
    T[1][1] = dp[0][0] + dp[2][0]
    T[1][2] = dp[0][1] + dp[2][1]
    T[2][0] = dp[0][1] + dp[1][1]
    T[2][1] = dp[0][2] + dp[1][2]
    T[2][2] = dp[0][0] + dp[1][0]
    dp, T = T, dp

m = sum(a) % 3

ans = 3 ** (n-1) - (dp[0][m] + dp[1][m] + dp[2][m])

check = 1
for i in range(n-1):
    if a[i] == a[i+1]:
        check = 0
        break

ans += check

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(10**6)

MOD = 998244353

ABC = "abc".index
*S, = map(ABC, input())
N = len(S)

def bruteforce(S):
    used = set()
    def dfs(s):
        key = tuple(s)
        if key in used:
            return
        used.add(key)
        for i in range(len(s)-1):
            if s[i] != s[i+1]:
                a = s[i]; b = s[i+1]
                s[i] = s[i+1] = 3 - a - b
                dfs(s)
                s[i] = a; s[i+1] = b
    dfs(S)
    return len(used)

if len(S) <= 3:
    print(bruteforce(S))
else:
    c = Counter(S)
    if c[0] == N or c[1] == N or c[2] == N:
        print(1)
    else:
        r3 = range(3); r2 = range(2)
        P = [[[0,0] for i in r3] for j in r3]
        Q = [[[0,0] for i in r3] for j in r3]
        P[0][0][0] = P[1][1][0] = P[2][2][0] = 1
        for i in range(N-1):
            for p in r3:
                for q in r3:
                    for r in r2:
                        Q[p][q][r] = 0
            for p in r3:
                for q in r3:
                    for r in r2:
                        for k in r3:
                            Q[k][(q+k)%3][r | (p == k)] += P[p][q][r] % MOD
            P, Q = Q, P
        ans = 0
        r = sum(S) % 3
        for i in r3:
            ans += P[i][r][1]
        if all(S[i] != S[i+1] for i in range(N-1)):
            ans += 1
        print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import itertools

S = input()
N = len(S)
if all(S[0] == c for c in S):
    print(1)
    exit()
if N == 2:
    print(1 if S[0]==S[1] else 2)
    exit()

if N == 3:
    def another(a,b):
        s = set('abc')
        s -= set([a,b])
        return list(s)[0]
    ptn = set()
    stack = [S]
    while stack:
        a = stack.pop()
        ptn.add(a)
        if a[0] != a[1]:
            b = another(a[0],a[1])*2 + a[2]
            if not b in ptn:
                stack.append(b)
        if a[1] != a[2]:
            c = a[0] + another(a[1],a[2])*2
            if not c in ptn:
                stack.append(c)
    print(len(ptn))
    exit()

#N >= 4
MOD = 998244353
dp = [[[[0 for u in range(2)] for l in range(3)] for s in range(3)] for n in range(N+1)]
#dp[n][sum%3][last][exist'xx'?]
for ptn in itertools.product(range(3),repeat=4):
    seq = (ptn[0]==ptn[1] or ptn[1]==ptn[2] or ptn[2]==ptn[3])
    dp[4][sum(ptn)%3][ptn[3]][seq] += 1

for n in range(4,N):
    for s in range(3):
        for l in range(3):
            for u in range(2):
                for l2 in range(3):
                    s2 = (s+l2)%3
                    u2 = u or l==l2
                    dp[n+1][s2][l2][u2] += dp[n][s][l][u]
                    dp[n+1][s2][l2][u2] %= MOD

sm = 0
for c in S:
    sm += ord(c) - ord('a')
seq = False
for c1,c2 in zip(S,S[1:]):
    if c1 == c2:
        seq = True
        break
ans = sum([dp[N][sm%3][i][1] for i in range(3)])
if not seq: ans += 1
print(ans % MOD)

Submission status: Accepted

Solution code:
s = input()
n = len(s)
flg = 0
for i in range(1,n):
  if s[i-1] != s[i]:
    flg += 1
if flg == 0:
  print(1)
  exit()
par = (s.count("a")+s.count("b")*2+2)%3
dp = [[0 for i in range(9)] for j in range(n)]
mod = 998244353
dp[0][0] = 1
dp[0][4] = 1
dp[0][8] = 1
for i in range(1,n):
  dp[i][0] = dp[i-1][5]+dp[i-1][8]
  dp[i][1] = dp[i-1][3]+dp[i-1][6]
  dp[i][2] = dp[i-1][4]+dp[i-1][7]
  dp[i][3] = dp[i-1][1]+dp[i-1][7]
  dp[i][4] = dp[i-1][2]+dp[i-1][8]
  dp[i][5] = dp[i-1][0]+dp[i-1][6]
  dp[i][6] = dp[i-1][0]+dp[i-1][3]
  dp[i][7] = dp[i-1][1]+dp[i-1][4]
  dp[i][8] = dp[i-1][2]+dp[i-1][5]
  for j in range(9):
    dp[i][j] %= mod
ans = pow(3,n-1,mod)-dp[-1][par]-dp[-1][par+3]-dp[-1][par+6]
if flg == n-1:
  ans += 1
if n == 3 and flg == n-1 and par == 2:
  ans -= 1
print(ans%mod)

Submission status: Accepted

Solution code:
def main():
    md = 998244353
    s = input()
    n = len(s)
    al = True  # allすべて同じ文字
    an = 1  # any連続が存在すると0
    for c0, c1 in zip(s, s[1:]):
        if c0 == c1:
            an = 0
        else:
            al = False
        if an == 0 and not al: break
    if al:
        print(1)
        exit()
    if n == 2:
        print(2)
        exit()
    if n == 3:
        if s[0] == s[-1]:
            print(7)
        elif s[0] == s[1] or s[1] == s[2]:
            print(6)
        else:
            print(3)
        exit()
    #print(n)
    #print(an)
    ord0=ord("a")
    r = sum(ord(c) - ord0 for c in s) % 3
    if n%3==0:
        d=pow(2,n//3-1,md)
        if r==0:
            an-=d*2
        else:
            an+=d
    print((pow(3, n - 1, md) - pow(2, n - 1, md) + an) % md)

main()

Submission status: Accepted

Solution code:
def main():
    md = 998244353
    s = input()
    n = len(s)
    if s.count(s[0]) == n:
        print(1)
        exit()
    if n == 2:
        print(2)
        exit()
    if n == 3:
        if s[0] == s[-1]:
            print(7)
        elif s[0] == s[1] or s[1] == s[2]:
            print(6)
        else:
            print(3)
        exit()
    ord0 = ord("a")
    a = [ord(c) - ord0 for c in s]
    r = sum(a) % 3
    dp = [[[[0] * 3 for _ in range(2)] for _ in range(3)] for _ in range(n)]
    for m in range(3):
        dp[0][m][0][m] = 1
    # print(a)
    # print(dp)
    for i in range(n - 1):
        for j in range(3):
            for k in range(2):
                for m in range(3):
                    pre = dp[i][j][k][m]  # iけた j余り k連続有無 m前の位
                    for nm in range(3):
                        nj = (j + nm) % 3
                        if nm == m:
                            dp[i + 1][nj][1][nm] = (dp[i + 1][nj][1][nm] + pre) % md
                        else:
                            dp[i + 1][nj][k][nm] = (dp[i + 1][nj][k][nm] + pre) % md
    d = 1
    for c0, c1 in zip(s, s[1:]):
        if c0 == c1:
            d = 0
            break
    print((sum(dp[n - 1][r][1]) + d) % md)

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import numpy as np

MOD = 998244353

S = input().rstrip()

arr = np.array(list(S.replace('a','0').replace('b','1').replace('c','2')),dtype=np.int32)

if (arr == arr[0]).all():
    print(1)
    exit()

def solve_naive(S):
    se = set([S])
    q = [S]
    while q:
        S = q.pop()
        for i in range(len(S)-1):
            x,y = S[i:i+2]
            if x == y:
                continue
            for t in 'abc':
                if t != x and t != y:
                    T = S[:i] + t+t + S[i+2:]
                    if T not in se:
                        q.append(T)
                        se.add(T)
    return len(se)

LS = len(S)
if LS < 6:
    answer = solve_naive(S)
    print(answer)
    exit()

# 適当な必要条件のもと全部作れる
# mod 3不変量
answer = pow(3,LS-1,MOD)
# 同一値の連続が存在しないものを間引く
if LS%3 == 0:
    x,y = (3+MOD)//2,0
    for _ in range(LS//3):
        x,y = 4*x+4*y,2*x+6*y
        x %= MOD
        y %= MOD
    if arr.sum()%3 == 0:
        answer -= x
    else:
        answer -= y
else:
    answer -= pow(2,LS-1,MOD)
# 初手に完成しているやつは使って良い
if (arr[:-1] != arr[1:]).all():
    answer += 1

answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
S=input()
N=len(S)
if N==3:
    if S[0]==S[1]:
        if S[1]==S[2]:
            print(1)
        else:
            print(6)
    else:
        if S[0]==S[2]:
            print(7)
        elif S[1]==S[2]:
            print(6)
        else:
            print(3)
    sys.exit()
a=S[0]
t=1
for i in range(N):
    if S[i]!=a:
        t=0
        break
if t==1:
    print(1)
    sys.exit()

mod=998244353
M=0
for s in S:
    if s=='b':
        M+=1
    elif s=='c':
        M+=2
    M%=3
dp=[]
for i in range(2):
    for k in range(3):
        for l in range(3):
            dp.append((i,k,l))
dd=[[[0]*3 for i in range(3)] for i in range(2)]
for i in range(3):
    dd[0][i][i]=1
for k in range(2,N+1):
    nd=[[[0]*3 for i in range(3)] for i in range(2)]
    for p in dp:
        con,moji,m=p
        n=dd[con][moji][m]
        #print(con,moji,m)
        if con==0:
            for k in range(3):
                if moji==k:
                    nd[1][k][ (m + k) % 3] += n
                    nd[1] [k ][(m + k) % 3] %=mod
                else:
                    nd[0][k][(m+k)%3]+=n
                    nd[0][ k] [(m+k) % 3] %=mod
        else:
            for k in range(3):
                nd[1][k][(m + k) % 3] += n
                nd[1][k][(m + k) % 3] %=mod
    #print(nd)
    dd=nd
flag=1
for i in range(N-1):
    if S[i]==S[i+1]:
        flag=0
ans=flag
for k in range(3):
    ans+=dd[1][k][M]
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
s = list(input())

n = len(s)

a = [0] * n

MOD = 998244353

for i in range(n):
    a[i] = ord(s[i]) - ord('a')

if max(a) == min(a):
    print(1)
    exit()
elif n == 3:
    def solver(m):
        x = m // 100
        y = ( m % 100 ) // 10
        z = m % 10
        if x != y:
            c = (3 - x - y) % 3
            temp = c * 110 + z
            if temp not in ans:
                ans.add(temp)
                solver(temp)
        if y != z:
            c = (3 - y - z) % 3
            temp = x * 100 + c * 11
            if temp not in ans:
                ans.add(temp)
                solver(temp)

    t = a[0] * 100 + a[1] * 10 + a[2]
    ans = set()
    ans.add(t)
    solver(t)
    print(len(ans))
    exit()
elif n == 2:
    print(2)
    exit()

dp = [[0,0,0] for _ in range(3)]

dp[0][0] = 1
dp[1][1] = 1
dp[2][2] = 1

for i in range(n-1):
    T = [[0,0,0] for _ in range(3)]
    T[0][0] = (dp[1][0] + dp[2][0]) % MOD
    T[0][1] = (dp[1][1] + dp[2][1]) % MOD
    T[0][2] = (dp[1][2] + dp[2][2]) % MOD
    T[1][0] = (dp[0][2] + dp[2][2]) % MOD
    T[1][1] = (dp[0][0] + dp[2][0]) % MOD
    T[1][2] = (dp[0][1] + dp[2][1]) % MOD
    T[2][0] = (dp[0][1] + dp[1][1]) % MOD
    T[2][1] = (dp[0][2] + dp[1][2]) % MOD
    T[2][2] = (dp[0][0] + dp[1][0]) % MOD
    dp, T = T, dp

m = sum(a) % 3

ans = 3 ** (n-1) - (dp[0][m] + dp[1][m] + dp[2][m])

check = 1
for i in range(n-1):
    if a[i] == a[i+1]:
        check = 0
        break

ans += check

#print(dp, 2 ** (n-1))

print(ans % MOD)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(10**6)

MOD = 998244353

ABC = "abc".index
*S, = map(ABC, input())
N = len(S)

def bruteforce(S):
    used = set()
    def dfs(s):
        key = tuple(s)
        if key in used:
            return
        used.add(key)
        for i in range(len(s)-1):
            if s[i] != s[i+1]:
                a = s[i]; b = s[i+1]
                s[i] = s[i+1] = 3 - a - b
                dfs(s)
                s[i] = a; s[i+1] = b
    dfs(S)
    return len(used)

if len(S) <= 3:
    print(bruteforce(S))
else:
    c = Counter(S)
    if c[0] == N or c[1] == N or c[2] == N:
        print(1)
    else:
        P = [[[0,0] for i in range(3)] for j in range(3)]
        Q = [[[0,0] for i in range(3)] for j in range(3)]
        P[0][0][0] = P[1][1][0] = P[2][2][0] = 1
        for i in range(N-1):
            for p in range(3):
                for q in range(3):
                    for r in range(2):
                        Q[p][q][r] = 0
            for p in range(3):
                for q in range(3):
                    for r in range(2):
                        for k in range(3):
                            Q[k][(q+k)%3][r | (p == k)] += P[p][q][r] % MOD
            P, Q = Q, P
        ans = 0
        r = sum(S) % 3
        for i in range(3):
            ans += P[i][r][1]
        if all(S[i] != S[i+1] for i in range(N-1)):
            ans += 1
        print(ans % MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


M = 998244353

def powmod(a, x, m = M):
    y = 1
    while 0 < x:
        if x % 2 == 1:
            y *= a
            y %= m
        x //= 2
        a = a ** 2
        a %= m

    return y


def solve(s):
    n = len(s)

    nb = nc = 0
    ch = s[0]
    if ch == 'b':
        nb += 1
    elif ch == 'c':
        nc += 1
    sf = True
    tf = True
    left = ch
    for ch in s[1:]:
        if ch == 'b':
            nb += 1
        elif ch == 'c':
            nc += 1
        if ch == left:
            sf = False
        else:
            tf = False
        left = ch


    if tf:
        return 1
    if n == 3:
        if (nb + nc * 2) % 3:
            return 7 if sf else 6
        else:
            return 3
    if n % 3:
        return (powmod(3, n - 1) + M - powmod(2, n - 1) + (1 if sf else 0)) % M
    else:
        if (nb + nc * 2) % 3:
            return (powmod(3, n - 1) + M - (powmod(2, n - 1) - powmod(2, n // 3 - 1)) + (1 if sf else 0)) % M
        else:
            return (powmod(3, n - 1) + M - (powmod(2, n // 3) + 4 * powmod(8, n // 3 - 1)) + (1 if sf else 0)) % M

def main():
    s = input()

    print(solve(s))


if __name__ == '__main__':
    main()