Problem:


Score : 900 points

Problem Statement

There are N Snukes lining up in a row.
You are given a string S of length N. The i-th Snuke from the front has two red balls if the i-th character in S is 0; one red ball and one blue ball if the i-th character in S is 1; two blue balls if the i-th character in S is 2.

Takahashi has a sequence that is initially empty. Find the number of the possible sequences he may have after repeating the following procedure 2N times, modulo 998244353:

Each Snuke who has one or more balls simultaneously chooses one of his balls and hand it to the Snuke in front of him, or hand it to Takahashi if he is the first Snuke in the row.

Takahashi receives the ball and put it to the end of his sequence.

Constraints

1 \leq |S| \leq 2000

S consists of 0,1 and 2.

Note that the integer N is not directly given in input; it is given indirectly as the length of the string S.

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of the possible sequences Takahashi may have after repeating the procedure 2N times, modulo 998244353.

Sample Input 1

02

Sample Output 1

3

There are three sequences that Takahashi may have: rrbb, rbrb and rbbr, where r and b stand for red and blue balls, respectively.

Sample Input 2

1210

Sample Output 2

55

Sample Input 3

12001021211100201020

Sample Output 3

543589959



Sample input:
02


Sample output:
3

Submission status: Wrong Answer

Solution code:
mod = 998244353
s = list(map(int, list(input())))
n = len(s)
dp = [[0]*(sum(s)+1) for _ in range(2*n+1)]
dp[0][0] = 1
curr = curb = 0
for i in range(2*n):
  if i < n:
    curb += s[i]
    curr += 2 - s[i]
  for j in range(min(i, curb)+1):
    if dp[i][j]:
      dp[i][j] %= mod
      if i - j < curr:
        dp[i+1][j] += dp[i][j]
      if j < curb:
        dp[i+1][j+1] += dp[i][j]
print(dp[2*n][curb])

Submission status: Wrong Answer

Solution code:
import os
import sys

import numpy as np
from scipy.misc import comb

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
# MOD = 10 ** 9 + 7
MOD = 998244353

S = list(map(int, list(sys.stdin.readline().rstrip())))
N = len(S)

# dp[i][c]: i まで決めた、使えるけど使ってない青が j 個余ってるパターン数
dp = np.zeros((N + 1, N * 2 + 10), dtype=int)
dp[0][0] = 1

for i in range(N):
    if S[i] == 2:
        # 青を使う
        dp[i + 1][1:] += dp[i][:-1]
        # 赤を使う
        dp[i + 1][2:i + 2] += dp[i][:i]
    if S[i] == 1:
        # 青を使う
        dp[i + 1] += dp[i]
        # 赤を使う
        dp[i + 1][1:] += dp[i][:-1]
    if S[i] == 0:
        # 青を使う
        dp[i + 1][:-1] += dp[i][1:]
        # 赤を使う
        dp[i + 1] += dp[i]
    dp[i + 1] %= MOD

# print(dp)
ans = 0
for c, cnt in enumerate(dp[-1]):
    # N から c 個選ぶ
    ans += comb(N, c, exact=True) * cnt
    ans %= MOD
    # print(N, c, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return list(sys.stdin.readline())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007

#A
"""
n,k = LI()
if 2*(k-1) < n:
    print("YES")
else:
    print("NO")
"""

#B
"""
c = LIR(3)
v = [[] for i in range(4)]
for i in range(3):
    c[i][0] -= 1
    c[i][1] -= 1
    v[c[i][0]].append(c[i][1])
    v[c[i][1]].append(c[i][0])

for i in range(4):
    li = [True for i in range(4)]
    li[i] = False
    q = [i]
    c = 0
    while q:
        x = q.pop(-1)
        k = 0
        for j in v[x]:
            if li[j]:
                li[j] = False
                q.append(j)
                if k == 0:
                    c += 1
                    k += 1
    if c == 3:
        print("YES")
        quit()
print("NO")
"""

#C
"""
k,a,b = LI()
if k <= a:
    print(k+1)
else:
    if b-a < 3:
        print(k+1)
    else:
        ans = a+((k-a+1)//2)*(b-a)+(k-a+1)%2
        print(ans)
"""

#D

#E
"""
n,m = LI()
a = LIR(n)
a.sort()
a = a[::-1]
for i in range(n):
    for j in range(i+1,n):
        s = 0
        while a[i][s] == 0 and s < m-1:s+=1
        if s < m and a[i][s] != 0:
            if a[j][s] > 0:
                for k in range(s,m):
                    a[j][k] -= 1*a[i][k]
                    a[j][k] = abs(a[j][k])
r = 0
for i in range(n):
    if sum(a[i]) > 0:r += 1
print((pow(2,n+m-1)-pow(2,n-r+m-1))%998244353)
"""

#F
mod = 998244353
s = list(sys.stdin.readline().strip())
n = len(s)
dp = [[0 for i in range(2*n+1)] for j in range(2*n+1)]
r = [0 for i in range(n)]
b = [0 for i in range(n)]
for i in range(n):
    b[i] = int(s[i])
    r[i] = 2-b[i]
for i in range(n-1):
    r[i+1] += r[i]
    b[i+1] += b[i]
r.insert(0,0)
b.insert(0,0)
if r[1] > 0:
    dp[1][1] = 1
for i in range(1,n+1):
    if b[i] < i:break
    if b[i] >= i:dp[i][0] = 1
for i in range(n+1,2*n+1):
    if b[-1] < i:break
    if b[-1] >= i:dp[i][0] = 1
for i in range(2,n+1):
    for j in range(1,i+1):
        if r[i] >= j:
            dp[i][j] += dp[i-1][j-1]
            dp[i][j] %= mod
        if b[i] >= i-j:
            dp[i][j] += dp[i-1][j]
            dp[i][j] %= mod
for i in range(n+1,2*n+1):
    for j in range(1,i+1):
        if r[n] >= j:
            dp[i][j] += dp[i-1][j-1]
            dp[i][j] %= mod
        if b[n] >= i-j:
            dp[i][j] += dp[i-1][j]
            dp[i][j] %= mod

print(dp[2*n][r[-1]])

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return list(sys.stdin.readline())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007

#A
"""
n,k = LI()
if 2*(k-1) < n:
    print("YES")
else:
    print("NO")
"""

#B
"""
c = LIR(3)
v = [[] for i in range(4)]
for i in range(3):
    c[i][0] -= 1
    c[i][1] -= 1
    v[c[i][0]].append(c[i][1])
    v[c[i][1]].append(c[i][0])

for i in range(4):
    li = [True for i in range(4)]
    li[i] = False
    q = [i]
    c = 0
    while q:
        x = q.pop(-1)
        k = 0
        for j in v[x]:
            if li[j]:
                li[j] = False
                q.append(j)
                if k == 0:
                    c += 1
                    k += 1
    if c == 3:
        print("YES")
        quit()
print("NO")
"""

#C
"""
k,a,b = LI()
if k <= a:
    print(k+1)
else:
    if b-a < 3:
        print(k+1)
    else:
        ans = a+((k-a+1)//2)*(b-a)+(k-a+1)%2
        print(ans)
"""

#D

#E
"""
n,m = LI()
a = LIR(n)
a.sort()
a = a[::-1]
for i in range(n):
    for j in range(i+1,n):
        s = 0
        while a[i][s] == 0 and s < m-1:s+=1
        if s < m and a[i][s] != 0:
            if a[j][s] > 0:
                for k in range(s,m):
                    a[j][k] -= 1*a[i][k]
                    a[j][k] = abs(a[j][k])
r = 0
for i in range(n):
    if sum(a[i]) > 0:r += 1
print((pow(2,n+m-1)-pow(2,n-r+m-1))%998244353)
"""

#F
mod = 998244353
s = list(sys.stdin.readline().strip())
n = len(s)
dp = [[0 for i in range(2*n+1)] for j in range(2*n+1)]
r = [0 for i in range(n)]
b = [0 for i in range(n)]
for i in range(n):
    b[i] = int(s[i])
    r[i] = 2-b[i]
for i in range(n-1):
    r[i+1] += r[i]
    b[i+1] += b[i]
r.insert(0,0)
b.insert(0,0)
if r[1] > 0:
    dp[1][1] = 1
for i in range(1,n+1):
    if b[i] < i:break
    if b[i] >= i:dp[i][0] = 1
for i in range(n+1,2*n+1):
    if b[-1] >= i:dp[i][0] = 1
for i in range(2,n+1):
    for j in range(1,i+1):
        if r[i] >= j:
            dp[i][j] += dp[i-1][j-1]
            dp[i][j] %= mod
        if b[i] >= i-j:
            dp[i][j] += dp[i-1][j]
            dp[i][j] %= mod
for i in range(n+1,2*n+1):
    for j in range(1,i+1):
        if r[n] >= j:
            dp[i][j] += dp[i-1][j-1]
            dp[i][j] %= mod
        if b[n] >= i-j:
            dp[i][j] += dp[i-1][j]
            dp[i][j] %= mod

print(dp[2*n][r[-1]])

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return list(sys.stdin.readline())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007

#A
"""
n,k = LI()
if 2*(k-1) < n:
    print("YES")
else:
    print("NO")
"""

#B
"""
c = LIR(3)
v = [[] for i in range(4)]
for i in range(3):
    c[i][0] -= 1
    c[i][1] -= 1
    v[c[i][0]].append(c[i][1])
    v[c[i][1]].append(c[i][0])

for i in range(4):
    li = [True for i in range(4)]
    li[i] = False
    q = [i]
    c = 0
    while q:
        x = q.pop(-1)
        k = 0
        for j in v[x]:
            if li[j]:
                li[j] = False
                q.append(j)
                if k == 0:
                    c += 1
                    k += 1
    if c == 3:
        print("YES")
        quit()
print("NO")
"""

#C
"""
k,a,b = LI()
if k <= a:
    print(k+1)
else:
    if b-a < 3:
        print(k+1)
    else:
        ans = a+((k-a+1)//2)*(b-a)+(k-a+1)%2
        print(ans)
"""

#D

#E
"""
n,m = LI()
a = LIR(n)
a.sort()
a = a[::-1]
for i in range(n):
    for j in range(i+1,n):
        s = 0
        while a[i][s] == 0 and s < m-1:s+=1
        if s < m and a[i][s] != 0:
            if a[j][s] > 0:
                for k in range(s,m):
                    a[j][k] -= 1*a[i][k]
                    a[j][k] = abs(a[j][k])
r = 0
for i in range(n):
    if sum(a[i]) > 0:r += 1
print((pow(2,n+m-1)-pow(2,n-r+m-1))%998244353)
"""

#F
mod = 998244353
s = list(sys.stdin.readline().strip())
n = len(s)
dp = [[0 for i in range(2*n+1)] for j in range(2*n+1)]
r = [0 for i in range(n)]
b = [0 for i in range(n)]
for i in range(n):
    b[i] = int(s[i])
    r[i] = 2-b[i]
for i in range(n-1):
    r[i+1] += r[i]
    b[i+1] += b[i]
r.insert(0,0)
b.insert(0,0)
if r[1] > 0:
    dp[1][1] = 1
for i in range(1,n+1):
    if b[i] < i:break
    if b[i] >= i:dp[i][0] = 1
for i in range(n+1,2*n+1):
    if b[-1] >= i:dp[i][0] = 1
for i in range(2,n+1):
    for j in range(1,i+1):
        if r[i] >= j:
            dp[i][j] += dp[i-1][j-1]
            dp[i][j] %= mod
        if b[i] >= i-j:
            dp[i][j] += dp[i-1][j]
            dp[i][j] %= mod
for i in range(n+1,2*n+1):
    for j in range(1,i+1):
        if r[n] >= j:
            dp[i][j] += dp[i-1][j-1]
            dp[i][j] %= mod
        if b[n] >= i-j:
            dp[i][j] += dp[i-1][j]
            dp[i][j] %= mod

ans = 0
for i in range(2*n+1):
    ans += dp[2*n][i]
    ans %= mod
print(ans)

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
s=input()
n=len(s)

DP=[[0 for i in range(2*n+1)] for j in range(2*n+1)]
DP[0][0]=1

ao=0

for i in range(1,2*n+1):
    if i<=n :
        ao+=int(s[i-1])
        aka=min(i,n)*2-ao
    #ao=sum(int(s[t]) for t in range(min(n,i)))
    #aka=min(i,n)*2-ao
    for j in range(0,min(ao+1,i+1)):
        DP[i][j]+=DP[i-1][j-1]
    for j in range(max(0,i-aka),i+1):
        DP[i][j]+=DP[i-1][j]

#print(DP)
print(sum(DP[2*n]))

Submission status: Wrong Answer

Solution code:
s=input()
n=len(s)

DP=[[0 for i in range(2*n+1)] for j in range(2*n+1)]
DP[0][0]=1

for i in range(1,2*n+1):
    ao=sum(int(s[t]) for t in range(min(i,n)))
    aka=min(i,n)*2-ao
    for j in range(0,min(ao+1,i+1)):
        DP[i][j]+=DP[i-1][j-1]
    for j in range(max(0,i-aka),i+1):
        DP[i][j]+=DP[i-1][j]

#print(DP)
print(sum(DP[2*n]))

Submission status: Wrong Answer

Solution code:
s=input()
n=len(s)

DP=[[0 for i in range(2*n+1)] for j in range(2*n+1)]
DP[0][0]=1

for i in range(1,2*n+1):
    ao=sum(int(s[t]) for t in range(min(i,n)))
    aka=min(i,n)*2-ao
    for j in range(0,i+1):
        if ao-j>=0 :
            DP[i][j]+=DP[i-1][j-1]
        if aka-(i-j)>=0 :
            DP[i][j]+=DP[i-1][j]

#print(DP)
print(sum(DP[2*n]))

Submission status: Wrong Answer

Solution code:
import numpy as np


def prepare(n):
    f = 1
    for i in range(2, n + 1):
        f = f * i % MOD
    inv = [1] * (n + 1)
    inv[n] = pow(f, MOD - 2, MOD)
    for i in range(n, 0, -1):
        inv[i - 1] = inv[i] * i % MOD
    return f, inv


MOD = 998244353
s = input()
n = len(s)
dp = np.zeros(n + 1, dtype=np.int64)
dp[0] = 1
b_all = 0
i, j = 0, 1
for k in range(n):
    b_all += int(s[k])
    ball = 2 * (k + 1)
    dp[i + 1:j + 1] += dp[i:j]
    dp %= MOD
    if j <= ball - b_all:
        j += 1
    else:
        dp[j] = 0
    if k - i < b_all:
        pass
    else:
        dp[i] = 0
        i += 1
r_all = 2 * n - b_all
f, inv = prepare(n)
ans = 0
for k in range(i, j):
    r = r_all - k
    b = n - r
    ans += dp[k] * f % MOD * inv[r] % MOD * inv[b]
    ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
S=input()
N=len(S)
d=[[0]*4001 for _ in range(4001)]
d[0][0]=1
x=0
for i in range(2*N):
	if i<N:
		x+=int(S[i])
		y=2*i+2-x
	for j in range(i+1):
		for k in range(2):
			if i-y<=j-k<x:d[j+1-k][i-j+k]+=d[j][i-j]%998244353
print(d[x][y])

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = list(map(int, list(input())))
    n = len(s)
    dp = [1]
    mod = 998244353
    for i, c in enumerate(s):
        dp2 = [0]*(i+2)
        for r in range(i+1):
            if r+c > 0:
                dp2[r+c-1] = (dp2[r+c-1]+dp[r]) % mod
            if i+2-r-c > 0:
                dp2[r+c] += (dp2[r+c]+dp[r]) % mod
        dp = dp2
    for i in range(n):
        dp2 = [0]*(n-i)
        for r in range(n-i+1):
            if r > 0:
                dp2[r-1] = (dp2[r-1]+dp[r]) % mod
            if n-i-r > 0:
                dp2[r] = (dp2[r]+dp[r]) % mod
        dp = dp2
    print(dp[0] % mod)


main()

Submission status: Time Limit Exceeded

Solution code:
"""

i回目では前からi人目の持っていた任意のボールを置ける
赤を何回採用したかでDP


"""

S = input()
N = len(S)
mod = 998244353

lis = [0] * (2*N+1)
lis[0] = 1
R = 0
B = 0

c = 0
for n in S:

    if n == "0":
        R += 2
    elif n == "1":
        R += 1
        B += 1
    else:
        B += 2

    nlis = [0] * (2*N+1)
    
    for i in range(2*N):

        if i < R:
            nlis[i+1] += lis[i]
            nlis[i+1] %= mod

        if c-i < B:
            nlis[i] += lis[i]
            nlis[i] %= mod

    lis = nlis
    c += 1


for loop in range(N):
    
    nlis = [0] * (2*N+1)
    
    for i in range(2*N):

        if i < R:
            nlis[i+1] += lis[i]
            nlis[i+1] %= mod

        if c-i < B:
            nlis[i] += lis[i]
            nlis[i] %= mod

    lis = nlis
    c += 1

print (sum(lis) % mod)

Submission status: Time Limit Exceeded

Solution code:
# 数え上げで制約が 2 乗っぽいのでどうせ dp だろという気持ちになる
# なんで入力が数字で与えられるのかを考えるとちょっと視界が開ける

# よく考えると、できる列の制約は
# 「赤い/青いボールはできる列の i 個目までに A[i]/B[i] 個使える」
# と表せることがわかる
# これに気付けばあとは
#     dp[i][j] := i 個目まで並べたとき赤いボールを j 個使う場合の数
# とした dp が自然と思いつく

from itertools import accumulate

def main():
    mod = 998244353
    B = list(map(int, input()))
    N = len(B)
    A = [2-b for b in B] + [0]*N
    B += [0] * N
    a = b = 0
    for i in range(2*N):
        b += B[i]
        if b > 0:
            b -= 1
            B[i] = 1
        a += A[i]
        if a > 0:
            a -= 1
            A[i] = 1

    A = list(accumulate(A))
    B = list(accumulate(B))

    dp = [[0]*(2*N+2) for _ in range(2*N+1)]
    dp[0][0] = 1
    for i, (a, b) in enumerate(zip(A, B), 1):
        for j in range(2*N+1):
            if i - b <= j <= a:
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod

    print(sum(dp[2*N]) % mod)

main()

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
import sys
sys.setrecursionlimit(10**9)
S = input()
N = len(S)
Sum = [0]*(N+1)
for i in range(1, N+1):
    Sum[i] = Sum[i-1]+int(S[i-1])
memo = [[-1]*(N*2+1) for _ in range(N*2+1)]
def dp(i, j):
    if memo[i][j]>=0:
        return memo[i][j]
    n = min(i+j+1, N)
    if i+j == N*2:
        return 1
    res = 0
    s = Sum[n]
    if i<s:
        res+=dp(i+1, j)
    if j<2*n-s:
        res+=dp(i, j+1)
    memo[i][j] = res
    return res%mod
print(dp(0, 0))

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
import sys
sys.setrecursionlimit(10**9)
S = input()
N = len(S)
Sum = [0]*(N+1)
for i in range(1, N+1):
    Sum[i] = Sum[i-1]+int(S[i-1])
from functools import lru_cache
@lru_cache(maxsize=10**8)
def dp(i, j):
    n = min(i+j+1, N)
    if i+j == N*2:
        return 1
    res = 0
    s = Sum[n]
    if i<s:
        res+=dp(i+1, j)
    if j<2*n-s:
        res+=dp(i, j+1)
    return res%mod
print(dp(0, 0))

Submission status: Time Limit Exceeded

Solution code:
s = input()
MOD = 998244353
cnt_r = []
cnt_b = []
for i in s:
    cnt_r.append(2-int(i))
    cnt_b.append(int(i))
cursum_cnt_r = [0]*(len(s)+1)
cursum_cnt_b = [0]*(len(s)+1)
for i in range(len(s)):
    cursum_cnt_r[i+1] = cursum_cnt_r[i] + cnt_r[i]
    cursum_cnt_b[i+1] = cursum_cnt_b[i] + cnt_b[i]
cursum_cnt_r = cursum_cnt_r + [cursum_cnt_r[-1]]*len(s)
cursum_cnt_b = cursum_cnt_b + [cursum_cnt_b[-1]]*len(s)

#dp[ni][ri]:nこのボールを並べたときに赤色のボールがri個含まれるときの並べ方総数
dp = [[0]*(2*len(s)+1) for i in range(2*len(s)+1)]
dp[0][0] = 1
for ni in range(1,2*len(s)+1):
    for ri in range(0,ni+1):
        if ri == 0:
            if 0 <= ni <= cursum_cnt_b[ni]:
                #青色を選ぶ
                dp[ni][ri] = dp[ni-1][ri]
        elif ri == ni:
            if 0 <= ri <= cursum_cnt_r[ni]:
                #赤色を選ぶ
                dp[ni][ri] = dp[ni-1][ri-1]
        else:
            if 0 <= ri <= cursum_cnt_r[ni] and 0 <= ni-ri <= cursum_cnt_b[ni]:
                dp[ni][ri] += dp[ni-1][ri]
                dp[ni][ri] += dp[ni-1][ri-1]
        dp[ni][ri] %= MOD 

print(max(dp[2*len(s)]))

Submission status: Time Limit Exceeded

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

MOD = 998244353  # type: int

def comb(n, k):
    if k > n:
        return 0
    k = min(k, n - k)
    ret = 1
    for i in range(k):
        ret *= n - i
        ret //= i + 1
    return ret

def solve(S: str):
    n = len(S)
    b_total = 0
    b_counts = []
    for c in S:
        b_total += ord(c) - ord('0')
        b_counts.append(b_total)
    dp = [[0] * (b_total + 1) for _ in range(2 * n + 1)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(min(i + 1, b_total + 1)):
            if b_counts[i] >= j + 1:
                dp[i + 1][j + 1] += dp[i][j]
            if (i + 1) * 2 - b_counts[i] >= (i + 1) - j:
                dp[i + 1][j] += dp[i][j]
    #    print(dp[i])
    #print(dp[n])
    ret = 0
    for b, val in enumerate(dp[n]):
        ret += val * comb(n, b_total - b)
    print(ret % MOD)
    return

    ##dp[0][0] = 1
    ##for i in range(2 * n):
    ##    for j in range(min(i + 1, b_total + 1)):
    ##        b_max = b_counts[i] if i < n else b_total
    ##        r_max = (i + 1) * 2 - b_max if i < n else 2 * n - b_total
    ##        if b_max >= j + 1:
    ##            dp[i + 1][j + 1] += dp[i][j]
    ##        if r_max >= (i + 1) - j:
    ##            dp[i + 1][j] += dp[i][j]
    ##ret = sum(dp[2 * n])
    ##print(ret % MOD)
    ##return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = str(next(tokens))
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

MOD = 998244353  # type: int

def solve(S: str):
    n = len(S)
    b_total = 0
    b_counts = []
    for c in S:
        b_total += ord(c) - ord('0')
        b_counts.append(b_total)
    dp = [[0] * (b_total + 1) for _ in range(2 * n + 1)]
    dp[0][0] = 1
    for i in range(2 * n):
        for j in range(min(i + 1, b_total + 1)):
            b_max = b_counts[i] if i < n else b_total
            r_max = (i + 1) * 2 - b_max if i < n else 2 * n - b_total
            if b_max >= j + 1:
                dp[i + 1][j + 1] += dp[i][j]
            if r_max >= (i + 1) - j:
                dp[i + 1][j] += dp[i][j]
    ret = sum(dp[2 * n])
    print(ret % MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = str(next(tokens))
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
mod=998244353

DP=[[0 for i in range(2*n+1)] for j in range(2*n+1)]
DP[0][0]=1

ao=0

for i in range(1,2*n+1):
    if i<=n :
        ao+=int(s[i-1])
        aka=i*2-ao
    #ao=sum(int(s[t]) for t in range(min(n,i)))
    #aka=min(i,n)*2-ao
    for j in range(0,min(ao+1,i+1)):
        DP[i][j]=(DP[i][j]+DP[i-1][j-1])%mod
    for j in range(max(0,i-aka),i+1):
        DP[i][j]=(DP[i][j]+DP[i-1][j])%mod

#print(DP)
print(DP[2*n][ao])

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
mod=998244353

DP=[[0 for i in range(2*n+1)] for j in range(2*n+1)]
DP[0][0]=1

ao=0

for i in range(1,2*n+1):
    if i<=n :
        ao+=int(s[i-1])
        aka=i*2-ao
    #ao=sum(int(s[t]) for t in range(min(n,i)))
    #aka=min(i,n)*2-ao
    for j in range(0,min(ao+1,i+1)):
        DP[i][j]=(DP[i][j]+DP[i-1][j-1])%mod
    for j in range(max(0,i-aka),i+1):
        DP[i][j]=(DP[i][j]+DP[i-1][j])%mod

#print(DP)
print(sum(DP[2*n])%mod)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
r = [0] * 2 * n
b = [0] * 2 * n

if s[0] == "0":
    r[0] = 2
elif s[0] == "1":
    r[0] = 1
    b[0] = 1
else:
    b[0] = 2

for i in range(1, n):
    if s[i] == "0":
        r[i] = r[i - 1] + 2
        b[i] = b[i - 1]
    elif s[i] == "1":
        r[i] = r[i - 1] + 1
        b[i] = b[i - 1] + 1
    else:
        r[i] = r[i - 1]
        b[i] = b[i - 1] + 2

for i in range(n, 2 * n):
    r[i] = r[n - 1]
    b[i] = b[n - 1]

dp = [[0 for i in range(0, 2 * n)] for j in range(0, r[-1] + 1)]

if b[0] > 0:
    dp[0][0] = 1

if r[0] > 0:
    dp[1][0] = 1

for k in range(1, 2 * n):
    if dp[0][k - 1] == 0:
        dp[0][k] = 0
    else:
        rk = r[k]
        bk = b[k] - k
        if bk > 0:
            dp[0][k] = 1
            
for j in range(1, r[-1] + 1):
    for k in range(1, 2 * n):
        if dp[j - 1][k - 1] > 0 and j - 1 < r[k]:
            dp[j][k] += dp[j - 1][k - 1]
        if dp[j][k - 1] > 0 and k - j < b[k]:
            dp[j][k] += dp[j][k - 1]
        dp[j][k] %= 998244353
    
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
r = [0] * 2 * n
b = [0] * 2 * n

if s[0] == "0":
    r[0] = 2
elif s[0] == "1":
    r[0] = 1
    b[0] = 1
else:
    b[0] = 2

for i in range(1, n):
    if s[i] == "0":
        r[i] = r[i - 1] + 2
        b[i] = b[i - 1]
    elif s[i] == "1":
        r[i] = r[i - 1] + 1
        b[i] = b[i - 1] + 1
    else:
        r[i] = r[i - 1]
        b[i] = b[i - 1] + 2

for i in range(n, 2 * n):
    r[i] = r[n - 1]
    b[i] = b[n - 1]

dp = [[0 for i in range(0, 2 * n)] for j in range(0, r[-1] + 1)]

if b[0] > 0:
    dp[0][0] = 1

if r[0] > 0:
    dp[1][0] = 1

for k in range(1, 2 * n):
    if dp[0][k - 1] == 0:
        dp[0][k] = 0
    else:
        rk = r[k]
        bk = b[k] - k
        if bk > 0:
            dp[0][k] = 1
            
for j in range(1, r[-1] + 1):
    for k in range(1, 2 * n):
        if dp[j - 1][k - 1] > 0 and j - 1 < r[k]:
            dp[j][k] += dp[j - 1][k - 1]
        if dp[j][k - 1] > 0 and k - j < b[k]:
            dp[j][k] += dp[j][k - 1]
    
print(dp[-1][-1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def tqdm(iterable): return iterable
def inpl(): return list(map(int, input().split()))
MOD = 998244353

S = input()
N = len(S)
B = [0]*N
R = [0]*N

for i in range(N):
    b = int(S[i])
    B[i] = b
    R[i] = 2 - b

DP = defaultdict(int)
DP[(B[0], R[0])] = 1

for i in tqdm(range(1, N)):
    DP2 = defaultdict(int)
    b1, r1 = B[i], R[i]
    for (b0, r0), v in DP.items():
        b2, r2 = b0+b1, r0+r1
        if b0:
            DP2[(b2-1, r2)] = (DP2[(b2-1, r2)] + v)%MOD
        if r0:
            DP2[(b2, r2-1)] = (DP2[(b2, r2-1)] + v)%MOD
    DP = DP2

for _ in tqdm(range(N+1)):
    DP2 = defaultdict(int)
    for (b, r), v in DP.items():
        if b:
            DP2[(b-1, r)] = (DP2[(b-1, r)] + v)%MOD
        if r:
            DP2[(b, r-1)] = (DP2[(b, r-1)] + v)%MOD
    DP = DP2

print(sum(DP.values()))

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
s = input()
n = len(s)
R = s.count("0") * 2 + s.count("1")
B = 2*n - R
rb = [[R, B] for _ in range(2*n)]
if s[0] == "0":
	rb[0] = [2, 0]
elif s[0] == "1":
	rb[0] = [1, 1]
else:
	rb[0] = [0, 2]
for i in range(1, n):
	if s[i] == "0":
		rb[i] = [rb[i-1][0] + 2, rb[i-1][1] + 0]
	elif s[i] == "1":
		rb[i] = [rb[i-1][0] + 1, rb[i-1][1] + 1]
	else:
		rb[i] = [rb[i-1][0] + 0, rb[i-1][1] + 2]

dp = [[0 for _ in range(R+1)] for _ in range(2*n)]
if rb[0][0] >= 1:
	dp[0][1] = 1
if rb[0][1] >= 1:
	dp[0][0] = 1
for i in range(1, 2*n):
	for j in range(R+1):
		if j > 0 and rb[i][0] >= j:
			dp[i][j] += dp[i-1][j-1]
			dp[i][j] %= MOD
		if j != i+1 and rb[i][1] >= i+1 - j:
			dp[i][j] += dp[i-1][j]
			dp[i][j] %= MOD

print(dp[2*n-1][R])

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)

from collections import defaultdict

reddic = defaultdict(int)
bludic = defaultdict(int)

redarray = [0] * (N+1)
bluarray = [0] * (N+1)

for e,c in enumerate(S):

    if c == "2":
        bludic[e+1] += 2
        bluarray[e+1] += 2
    elif c == "1":
        reddic[e+1] += 1
        bludic[e+1] += 1

        redarray[e+1] += 1
        bluarray[e+1] += 1
    elif c == "0":
        reddic[e+1] += 2
        redarray[e+1] += 2

for i in range(1,N+1):
    redarray[i] += redarray[i-1]
    bluarray[i] += bluarray[i-1]

# print("redarray: ", redarray)
# print("bluarray: ", bluarray)

dp = [ [0] * (2*N+1) for _ in range(2*N+1)]
dp[0][0] = 1
MOD = 998244353

for p in range(1, 2*N+1):
    for r in range(0, p):
        idx = p if p <= N else N
        if r < redarray[idx]:
            dp[p][r+1] += dp[p-1][r] % MOD
        if p-1-r < bluarray[idx]:
            dp[p][r] += dp[p-1][r] % MOD
    # print("{:3d}".format(p), dp[p])

print(dp[2*N][redarray[N]]%MOD)

Submission status: Time Limit Exceeded

Solution code:
S = input()
n = len(S)
N = n
# --------------------------------------------------------------------------------
from bisect import bisect_left, bisect_right
# getred = lambda c: 2 if c == "0" else 1 if c == "1" else 0
redidx = []
blueidx = []
for e,c in enumerate(S):
    if c == "2":
        blueidx.append(e+1)
        blueidx.append(e+1)
    elif c == "1":
        blueidx.append(e+1)
        redidx.append(e +1)
    elif c == "0":
        redidx.append(e+1)
        redidx.append(e+1)
dp = [[0] * (2*N+1) for _ in range(2*N+1)]
dp[0][0] = 1

# print("redidx: ", redidx)
# print("blueidx: ", blueidx)


MOD = 998244353
for p in range(1,2*N+1): # p$B2sL\$N%?!<%s$G!"(Br$B8D@V$$6L$r;H$C$F$$$k(B
    for r in range(0,p): # r $B$OA0$N%?!<%s$N(B 0<=r<=p, $BA0$N%?!<%s$G(Bp$B;H$C$F$k$N$O$"$j$($J$$(B

        if r < bisect_right(redidx, p):
            dp[p][r+1] += dp[p-1][r]  % MOD

        if p-1-r < bisect_right(blueidx, p):
            dp[p][r] += dp[p-1][r] % MOD

        # print("p: {p}, r: {r} , dp[{p}]: {dp}, r:{r}, bitright redidx,p: {bit} b:{b}: bitright_blueidx,p: {bit2}".format(p=p, r=r, dp=dp[p], bit=bisect_right(redidx,p), bit2=bisect_right(blueidx,p), b=p-1-r))
        # print("\tredidx: {red},\n\tbluidx: {blu}".format(red=redidx, blu=blueidx))

# print(sum(dp[2*N][len(redidx)]))
print(dp[2*N][len(redidx)] % MOD)
        
# print(redidx)
# print(blueidx)
exit(0)


# --------------------------------------------------------------------------------

sumred = [0] * (n+1)
sumblu = [0] * (n+1)
getred = lambda c: 2 if c == "0" else 1 if c == "1" else 0
# getblu = lambda c: 2 - getred(c)

sumred[0] = 0 # getred(S[0])
sumblu[0] = 0 # getred(S[0])
# sumred[1] = getred(S[0])

for i in range(1,n+1): # i $B?ML\$^$G8+$?;~$N;H$($k@V$$6L$N9g7W(B
    sumred[i] = sumred[i-1] + getred(S[i-1])
    sumblu[i] = sumblu[i-1] + 2 - getred(S[i-1])

dp = [ [0] * (2*N+1) for _ in range(2*N+1)] 

dp[0][0] = 0
dp[0][1] = 0
# dp[1][0] = $B$b$7(B1$B?ML\$,@D$$6L$N$_$@$C$?$i(B($B!"(B
# dp[1][0] = 1$B2sL\!"(B1$B?ML\$,@D$$6L$N$_$@$C$?$i"*(B1$BDL$j(B
# dp[1][0] = 1$B2sL\!"(B1$B?ML\$,@D!&@VN>J};}$C$F$?$i"*(B1$BDL$j(B
# dp[1][1] = 1$B2sL\!"(B1$B?ML\$,(B $BF1>e(B  1$BDL$j(B
# dp[1][2] = $B$J$7(B
dp[1][0] = 1
dp[1][1] = 1


for p in range(1,2*N+1):
    # p$B%?!<%sL\$G!"(Bp$B8D$N6L$r;H$C$F$$$k!#(B
    # $B@D$K$h$C$F:GDc?t$K$b@)Ls$r$+$1$kI,MW$,$"$k!#(B
    # $B;H$($k@D$N6L$N:GBg?t$O!"(Bsumblu[p]$B8D(B
    # i$B?ML\!!(B

    if p <= N:
        for r in range(max(0,p-sumblu[p]), min(sumred[p], p)+1): 
            print("p: {}, r: {}".format(p,r))

            if r > 0:
                dp[p][r] += dp[p-1][r-1]
                dp[p][r] += dp[p-1][r]
            else:
                dp[p][r] += dp[p-1][r]

            print("dp[{p}][{r}] += dp[{a}][{b}]:{d} + dp[{a}][{c}]:{e}".format(p=p,r=r, a=p-1, b=r-1, c=r, d=dp[p-1][r-1], 
                e=dp[p-1][r]))

            dp[p][r] += dp[p-1][r-1] + dp[p-1][r]
    else:
        for r in range(max(0,p-sumblu[N]), min(sumred[N], p)+1): 
            print("p: {}, r: {}".format(p,r))

            if r > 0:
                dp[p][r] += dp[p-1][r-1]
                dp[p][r] += dp[p-1][r]
            else:
                dp[p][r] += dp[p-1][r]

            print("dp[{p}][{r}] += dp[{a}][{b}]:{d} + dp[{a}][{c}]:{e}".format(p=p,r=r, a=p-1, b=r-1, c=r, d=dp[p-1][r-1], 
                e=dp[p-1][r]))

            dp[p][r] += dp[p-1][r-1] + dp[p-1][r]

    print("\t",dp[p][r])
print(dp[2*N][r])

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
mod = 998244353

R = [0] * n
B = [0] * n
for i in range(n):
    if s[i] == '0':
        R[i] = 2
    elif s[i] == '1':
        R[i] = 1
        B[i] = 1
    else:
        B[i] = 2

for i in range(n-1):
    R[i+1] += R[i]
    B[i+1] += B[i]


dp = [[0] * (2*n+10) for _ in range(2*n+10)]

if R[0] > 0:
    dp[0][1] = 1
if B[0] > 0:
    dp[0][0] = 1

for i in range(n-1):
    for r in range(2*n+1):
        if R[i+1] >= r+1:
            dp[i+1][r+1] += dp[i][r]
            dp[i+1][r+1] %= mod
        if i+2-r < 0:
            break
        if B[i+1] >= i+2-r:
            dp[i+1][r] += dp[i][r]
            dp[i+1][r] %= mod

for i in range(n-1, 2*n-1):
    for r in range(2*n+1):
        if R[n-1] >= r+1:
            dp[i + 1][r + 1] += dp[i][r]
            dp[i + 1][r + 1] %= mod
        if i+2-r < 0:
            break
        if B[n-1] >= i+2-r:
            dp[i+1][r] += dp[i][r]
            dp[i+1][r] %= mod

ans = 0
for r in range(2*n+1):
    ans += dp[2*n-1][r]
    ans %= mod

print(ans)