AtCoder Regular Contest 094 - Normalization

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-----
abc

-----Sample Output-----
3

abc, aaa and ccc can be obtained.

Source: atcoder | Difficulty: VERY_HARD


Solutions:
def main():
	a = 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 range(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 range(l - 1))):
		ans += 1
	mod = 998244353
	dp = (1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0)
	for i in range(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()


import sys
readline = sys.stdin.readline
read = sys.stdin.read

def solve():
	s = input()
	n = len(s)
	if all((s[0] == k for k in s)):
		return 1
	somesame = 0
	for j in range(n - 1):
		if s[j] == s[j + 1]:
			somesame = 1
			break
	x = [(ord(i) - 1) % 3 for i in s]
	v = sum(x) % 3
	if n == 2:
		return 2
	if n == 3:
		if v == 0:
			return 3
		if somesame == 0:
			return 7
		else:
			return 6
	dp = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
	for _ in range(n - 1):
		ndp = [[0] * 3 for i in range(3)]
		for i in range(3):
			for j in range(3):
				for k in range(3):
					if k == j:
						continue
					ndp[(i + k) % 3][k] += dp[i][j]
					ndp[(i + k) % 3][k] %= MOD
		dp = ndp
	c = pow(3, n - 1, MOD)
	c -= sum(dp[v])
	if somesame == 0:
		c += 1
	return c % MOD
MOD = 998244353
print(solve())


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
	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]
					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()


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 = [[[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))


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)
	elif 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]
		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
	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)


def main():
	md = 998244353
	s = input()
	n = len(s)
	al = True
	an = 1
	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)
		return
	if n == 2:
		print(2)
		return
	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)
		return
	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()


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
	elif (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))
main()


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)


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)


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)
	return
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))
	return
elif n == 2:
	print(2)
	return
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(ans % MOD)


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)
	return

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)
	return
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)


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()
MOD = 998244353
dp = [[[0 for u in range(2)] for l in range(3)] for s in range(3)]
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)


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))


M = 998244353
s = input()
n = len(s) - 1
v = sum(map(ord, s))
print((pow(3, n, M) - pow(2, n, M) + pow(2, n // 3, M) * (n % 3 == 2) * (1 - 3 * (v % 3 == 0)) + all((s[i] != s[i + 1] for i in range(n))) - (v == 294) - 1) * any((s[0] != k for k in s)) % M + 1)