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

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

dp = [[0]*(N+1) for i in range(N+1)] #dp[r][b]
if S[0] == '0':
    dp[0][1] = 1
elif S[0] == '1':
    dp[1][0] = 1
    dp[0][1] = 1
else:
    dp[1][0] = 1

for k in range(1,N):
    c = int(S[k])
    for r in range(k+1):
        b = k-r
        if c == 1:
            dp[r][b+1] += dp[r][b]
            dp[r][b+1] %= MOD
            dp[r+1][b] += dp[r][b]
            dp[r+1][b] %= MOD
        elif c == 0:
            dp[r][b+1] += dp[r][b]
            dp[r][b+1] %= MOD
            if r > 0:
                dp[r-1][b+2] += dp[r][b]
                dp[r-1][b+2] %= MOD
        else:
            if b > 0:
                dp[r+2][b-1] += dp[r][b]
                dp[r+2][b-1] %= MOD
            dp[r+1][b] += dp[r][b]
            dp[r+1][b] %= MOD

M = N+5
fac = [1,1] + [0]*M
finv = [1,1] + [0]*M
inv = [0,1] + [0]*M
for i in range(2,M+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def ncr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

ans = 0
for k in range(N+1):
    ans += ncr(N,k) * dp[k][N-k]

print(ans % MOD)

Submission status: Accepted

Solution code:
s = input()
N = len(s)
P = 998244353
B = 0
R = 0

Y = [[0] * (2*N+1) for _ in range(2*N+1)] # Block

for i in range(N):
    if s[i] == "0":
        R += 2
    elif s[i] == "1":
        B += 1
        R += 1
    else:
        B += 2
        
    # print(i, B, R)
    if R < i+1:
        for j in range(i+1-R):
            Y[R+1][j] = 1
    
    if B < i+1:
        for j in range(i+1-B):
            Y[j][B+1] = 1

X = [[0] * (B+1) for _ in range(R+1)]

for i in range(R+1):
    for j in range(B+1):
        if i == 0 and j == 0:
            X[i][j] = 1
            continue
        
        if Y[i][j]:
            continue
            
        if j > 0:
            X[i][j] += X[i][j-1]
        
        if i > 0:
            X[i][j] += X[i-1][j]
            
        X[i][j] %= P

print(X[-1][-1])

Submission status: Runtime Error

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

FACT=[1]
for i in range(1,2*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

R=0
B=0

RB=[[0,0]]*N

for i in range(N):
    s=S[i]
    if s=="0":
        R+=2
    elif s=="1":
        R+=1
        B+=1
    else:
        B+=2
    RB[i]=[R,B]

DP=[0]*(R+1)
DP[0]=1

for i in range(N):
    NDP=[0]*(R+1)
    red,blue=RB[i]
    for r in range(R+1):
        if DP[r]==0:
            continue
        if r+1<=red:
            NDP[r+1]+=DP[r]
        if i-r+1<=blue:
            NDP[r]+=DP[r]
    DP=NDP


ANS=0
for r in range(N+1):
    red=RB[-1][0]-r
    blue=RB[-1][1]-(N-r)

    ANS=ANS+DP[r]*Combi(red+blue,blue)
    ANS%=mod
print(ANS)

Submission status: Runtime Error

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

Solution code:
mod = 998244353
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=1000)
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: Runtime Error

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])
    comb = [0] * (n + 1)
    comb[0] = 1
    for i in range(n):
        comb[i + 1] = comb[i] * (n - i) // (i + 1)
    ret = 0
    for b, val in enumerate(dp[n]):
        #ret += val * comb(n, b_total - b)
        ret += val * comb[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: Runtime Error

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,2*n+1):
    if b[i] < i:break
    if b[min(i,n)] >= i:dp[i][0] = 1
for i in range(2,n+1):
    for j in range(1,2*n+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,2*n+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: Runtime Error

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

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

rk = 0
bk = 0

if s[0] == "0":
    rk = 2
elif s[0] == "1":
    rk = 1

bk = 2 - rk

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

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