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: Accepted

Solution code:
def solve(s):
    if all(a == b for a, b in zip(s, s[1:])):
        return 1
    if len(s) == 2:
        return 2
    elif len(s) == 3:
        if s[0] == s[1] or s[1] == s[2]:
            return 6
        elif s[0] == s[2]:
            return 7
        else:
            return 3
    # dp[has succession=0][mod 3][last char], dp[has succession=1][mod 3]
    dp = [[[0] * 3 for _ in range(3)], [0] * 3]
    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)], [0] * 3]
        dp0, dp1 = dp
        ndp0, ndp1 = ndp
        sdp1 = sum(dp1)
        ndp0[0][0] = (dp0[0][1] + dp0[0][2]) % MOD
        ndp0[1][0] = (dp0[1][1] + dp0[1][2]) % MOD
        ndp0[2][0] = (dp0[2][1] + dp0[2][2]) % MOD
        ndp0[0][1] = (dp0[2][0] + dp0[2][2]) % MOD
        ndp0[1][1] = (dp0[0][0] + dp0[0][2]) % MOD
        ndp0[2][1] = (dp0[1][0] + dp0[1][2]) % MOD
        ndp0[0][2] = (dp0[1][0] + dp0[1][1]) % MOD
        ndp0[1][2] = (dp0[2][0] + dp0[2][1]) % MOD
        ndp0[2][2] = (dp0[0][0] + dp0[0][1]) % MOD
        ndp1[0] = (dp0[0][0] + dp0[1][2] + dp0[2][1] + sdp1) % MOD
        ndp1[1] = (dp0[1][0] + dp0[2][2] + dp0[0][1] + sdp1) % MOD
        ndp1[2] = (dp0[2][0] + dp0[0][2] + dp0[1][1] + sdp1) % MOD
        dp = ndp
    return (dp[1][sum(map(ord, s)) % 3] + all(a != b for a, b in zip(s, s[1:]))) % MOD


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

Submission status: Accepted

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)]
#dp[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[sum(ptn)%3][ptn[3]][seq] += 1

for n in range(4,N):
    dp2 = [[[0 for u in range(2)] for l in range(3)] for s in range(3)]
    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
                    dp2[s2][l2][u2] += dp[s][l][u]
                    dp2[s2][l2][u2] %= MOD
    dp = dp2

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[sm%3][i][1] for i in range(3)])
if not seq: ans += 1
print(ans % MOD)

Submission status: Accepted

Solution code:
def solve(s):
    if all(a == b for a, b in zip(s, s[1:])):
        return 1
    if len(s) == 2:
        return 2
    elif len(s) == 3:
        if s[0] == s[1] or s[1] == s[2]:
            return 6
        elif s[0] == s[2]:
            return 7
        else:
            return 3
    # dp[has succession][mod 3][last char]
    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)]
        dp0, dp1 = dp
        ndp0, ndp1 = ndp
        sdp10, sdp11, sdp12 = sum(dp1[0]), sum(dp1[1]), sum(dp1[2])
        ndp0[0][0] = (dp0[0][1] + dp0[0][2]) % MOD
        ndp0[1][0] = (dp0[1][1] + dp0[1][2]) % MOD
        ndp0[2][0] = (dp0[2][1] + dp0[2][2]) % MOD
        ndp0[0][1] = (dp0[2][0] + dp0[2][2]) % MOD
        ndp0[1][1] = (dp0[0][0] + dp0[0][2]) % MOD
        ndp0[2][1] = (dp0[1][0] + dp0[1][2]) % MOD
        ndp0[0][2] = (dp0[1][0] + dp0[1][1]) % MOD
        ndp0[1][2] = (dp0[2][0] + dp0[2][1]) % MOD
        ndp0[2][2] = (dp0[0][0] + dp0[0][1]) % MOD
        ndp1[0][0] = (dp0[0][0] + sdp10) % MOD
        ndp1[1][0] = (dp0[1][0] + sdp11) % MOD
        ndp1[2][0] = (dp0[2][0] + sdp12) % MOD
        ndp1[0][1] = (dp0[2][1] + sdp12) % MOD
        ndp1[1][1] = (dp0[0][1] + sdp10) % MOD
        ndp1[2][1] = (dp0[1][1] + sdp11) % MOD
        ndp1[0][2] = (dp0[1][2] + sdp11) % MOD
        ndp1[1][2] = (dp0[2][2] + sdp12) % MOD
        ndp1[2][2] = (dp0[0][2] + sdp10) % MOD
        dp = ndp
    return (sum(dp[1][sum(map(ord, s)) % 3]) + all(a != b for a, b in zip(s, s[1:]))) % MOD


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

Submission status: Accepted

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
    if all(a == b for a, b in zip(s, s[1:])):
        return 1
    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: Accepted

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[3]+dp[8]+s)%mod,(dp[2]+dp[4]+dp[6]+s)%mod)
    print (ans + dp[9+x%3]) % mod
main()

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

def main():
    md = 998244353
    s = input()[:-1]
    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):
        dpi = dpi1
        dpi1 = dp[i + 1]
        for j in range(3):
            dpij = dpi[j]
            for k in range(2):
                dpijk = dpij[k]
                for m in range(3):
                    pre = dpijk[m]  # iけた j余り k連続有無 m前の位
                    for nm in range(3):
                        nj = (j + nm) % 3
                        if nm == m:
                            dpi1[nj][1][nm] = (dpi1[nj][1][nm] + pre) % md
                        else:
                            dpi1[nj][k][nm] = (dpi1[nj][k][nm] + pre) % md
    d = 1
    for a0, a1 in zip(a, a[1:]):
        if a0 == a1:
            d = 0
            break
    print((sum(dp[n - 1][r][1]) + d) % md)

main()

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
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)

        print(bara, zorome)


if __name__ == '__main__':
    F()

Submission status: Runtime Error

Solution code:
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+2)%3][(a+2)%3] += dp[i-1][p][a]
print(dp)
print(3**(len(S)-1) - dp[L-1][c%3][0] - dp[L-1][c%3][1] - dp[L-1][c%3][2] + (1-flag2))

Submission status: Runtime Error

Solution code:
import sys

S=int(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)]
for a in range(3)
dp[1][a][a]=1
for i in range(L):
    for p in range(3):
        for a in range(3)
        dp[i][p+(a+1)%3][(a+1)%3] += dp[i-1][p][a] 
        dp[i][p+(a+2)%3][(a+2)%3] += dp[i-1][p][a] 

print(3**(len(S)-1) + dp[L][c%3][0] + dp[L][c%3][1]+ dp[L][c%3][2] + (1-flag2))