Problem:


Score : 800 points

Problem Statement

Given is a string S consisting of 0 and 1. Find the number of strings, modulo 998244353, that can result from applying the following operation on S between 0 and K times (inclusive):

Choose a pair of integers i, j (1\leq i < j\leq |S|) such that the i-th and j-th characters of S are 0 and 1, respectively. Remove the j-th character from S and insert it to the immediate left of the i-th character.

Constraints

1 \leq |S| \leq 300

0 \leq K \leq 10^9

S consists of 0 and 1.

Input

Input is given from Standard Input in the following format:

S K

Output

Find the number of strings, modulo 998244353, that can result from applying the operation on S between 0 and K times (inclusive).

Sample Input 1

0101 1

Sample Output 1

4

Four strings, 0101, 0110, 1001, and 1010, can result.

Sample Input 2

01100110 2

Sample Output 2

14

Sample Input 3

1101010010101101110111100011011111011000111101110101010010101010101 20

Sample Output 3

113434815



Sample input:
0101 1


Sample output:
4

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 998244353
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

mod = 998244353 #出力の制限
N = 10**5
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
# a = cmb(n,r)

ss,k = input().split()

kk = int(k)

po = s(ss)

ans = 0

dp = [0 for i in range(200*200+1)]
dp[0] = 1
count = 0
pre = -1

for i in range(len(po)):
	if po[i][0] == "0":
		count += po[i][1]
	else:
		if count != 0:
			pre += 1
		for j in range(po[i][1]):
			j += 1
			for k in range(200*200,j-1,-1):
				if dp[k-j] != 0:
					dp[k] += dp[k-j] * cmb(count-1+j,j) - (k-j)
				dp[k] %= mod


for i in range(kk+1):
	ans += dp[i]
	ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
MOD = 998244353


def solve(s, k):
    one_count = []
    ones = 0
    for st in s:
        if st == "1":
            ones += 1
        else:
            one_count.append(ones)
            ones = 0
    one_count.append(ones)
    s = sum(one_count)
    m = len(one_count)
    dp = [[[0] * s for _ in range(s)] for __ in range(m + 1)]
    dp[0][0][0] = 1
    for i in range(m):
        c = one_count[i]
        for j in range(s):
            for p in range(s):
                dp[i][j][p] %= MOD
                for q in range(s - max(j, p)):
                    dp[i + 1][j + q][p + q] += dp[i][j][p]
                for q in range(-c, 0):
                    if j + q >= 0:
                        dp[i + 1][j + q][p] += dp[i][j][p]

    # print(dp)
    res = sum([dp[m][0][p] for p in range(min(k + 1, s))])
    # print(res)
    return res % MOD


def main():
    s, k_ = input().split()
    k = int(k_)
    res = solve(s, k)
    print(res)


def test():
    assert solve("0101", 1) == 4
    assert solve("01100110", 2) == 14
    assert solve("1101010010101101110111100011011111011000111101110101010010101010101", 20) == 113434815


if __name__ == "__main__":
    test()
    main()

Submission status: Runtime Error

Solution code:
mod = 998244353
S, K = input().split()
K = int(K)
cnt = 0
Cnt = []
for c in S:
    if c == "1":
        cnt += 1
    else:
        Cnt.append(cnt)
        cnt = 0
if cnt:
    Cnt.append(cnt)
n_groups = len(Cnt)
n_1s = S.count("1")

# dp[i][k][r] := i グループ目まで見て、すでに k 個動かしていて、
#                すでに動かした "1" の右端が r グループ目の場合の数
#     = dp[i-1][k][r]  # 動かさない場合
#      + sum(dp[i][k-1][0:r])  # 動かす場合
print(n_1s, n_groups)
print("Cnt=", Cnt)

ans = 0
dp = [[[0]*(n_groups+1) for _ in range(n_1s+2)] for _ in range(n_groups+1)]
cnt_cumsum = 0
dp[1][0][1] = 1
for i, cnt in enumerate(Cnt, 1):  # n_groups
    cnt_cumsum += cnt
    for k in range(cnt_cumsum+1):  # n_1s
        for r in range(1, i):
            if i==1 and k==0 and r==1:
                continue
            dp[i][k][r] = dp[i-1][k][r]
            if cnt < k:
                continue
            for r_ in range(r+1):
                dp[i][k][r] += dp[i][k-1][r_]
            dp[i][k][r] %= mod
ans = 0
for k in range(n_1s+1):
    print(dp[3][k])
    for r in range(n_groups+1):
        a = dp[n_groups][k][r]
        ans += a
print(ans % mod)

Submission status: Runtime Error

Solution code:
MOD = 998244353


def solve(s, k):
    one_count = []
    ones = 0
    for st in s:
        if st == "1":
            ones += 1
        else:
            one_count.append(ones)
            ones = 0
    one_count.append(ones)
    s = sum(one_count)
    m = len(one_count)
    dp = [[[0] * s for _ in range(s)] for __ in range(m + 1)]
    dp[0][0][0] = 1
    for i in range(m):
        c = one_count[i]
        for j in range(s):
            for p in range(s):
                dp[i][j][p] %= MOD
                for q in range(s - max(j, p)):
                    dp[i + 1][j + q][p + q] += dp[i][j][p]
                for q in range(-c, 0):
                    if j + q >= 0:
                        dp[i + 1][j + q][p] += dp[i][j][p]

    # print(dp)
    res = sum([dp[m][0][p] for p in range(min(k + 1, s + 1))])
    # print(res)
    return res % MOD


def main():
    s, k_ = input().split()
    k = int(k_)
    res = solve(s, k)
    print(res)


def test():
    assert solve("0101", 1) == 4
    assert solve("01100110", 2) == 14
    assert solve("1101010010101101110111100011011111011000111101110101010010101010101", 20) == 113434815


if __name__ == "__main__":
    test()
    main()

Submission status: Runtime Error

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

P = 998244353
def mod_prod(a,b):
    return (a % P) * (b % P) % P

def mod_fact(a):
    ret = 1
    for i in range(a):
        ret = ret * (i + 1) % P
    return ret

def mod_pow(a, n):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % P
        a = a * a % P
        n = n >> 1
    return ret

def mod_div(a, b):
    b_inv = mod_pow(b, P - 2)
    return a * b_inv % P

def mod_comb(a,b):
    ret = 1
    b = min(b, a - b)
    for i in range(b):
        ret *= a - i
        ret %= P
    ret = mod_div(ret, mod_fact(b))
    return ret

def solve():
    S, K = readline().split()
    K = int(K)

    N = len(S)
    N0 = S.count('0')
    N1 = S.count('1')

    ini_c = [0] * N1
    c0, c1 = 0, 0
    for i,c in enumerate(S):
        if c == '1':
            ini_c[c1] = N0 - c0
            c1 += 1
        else:
            c0 += 1

    REM = N0 - K

    if REM <= 0:
        # 全部動かせる
        dp = [[0] * N1 for i in range(N0 + 1)]
        dp[N0][0] = 1
        for i in range(N0 - 1, -1, -1):
            dp[i][0] = dp[i+1][0] + 1 if i >= ini_c[0] else dp[i+1][0]
        
        for j in range(1, N1):
            dp[N0][j] = 1
        
        for i in range(N0 - 1, -1, -1):
            for j in range(1, N1):
                dp[i][j] = dp[i+1][j] + dp[i][j-1] if i >= ini_c[j] else dp[i+1][j]
                dp[i][j] %= P

        print(dp[0][N1 - 1])
        return
    else:
        dp = [[[0] * N1 for i in range(N0 + 1)] for j in range(REM + 1)]
        
        if N0 > ini_c[0]:
            dp[0][N0][0] = 1
        
        for i in range(N0 - 1, -1, -1):
            dp[0][i][0] = dp[0][i+1][0] + (1 if i > ini_c[0] else 0)
        
        for j in range(1, N1):
            dp[0][N0][j] = 1 if ini_c[j] < N0 else 0

        for i in range(N0 - 1, -1, -1):
            for j in range(1, N1):
                dp[0][i][j] = dp[0][i+1][j] + (dp[0][i][j-1] if i > ini_c[j] else 0)
        
        for k in range(1, REM + 1):
            for i in range(N0, -1, -1):
                for j in range(N1):
                    dp[k][i][j] = (
                        (dp[k][i+1][j] if i+1 <= N0 else 0)
                        + (dp[k][i][j-1] if j-1>=0 and i > ini_c[j] else 0)
                        + (dp[k-1][i][j-1] if j-1>=0 and i==ini_c[j] else 0)
                    )
                    if j == 0 and i == ini_c[0]:
                        dp[k][i][j] += 1
        
        print(sum(dp[k][0][N1-1] for k in range(REM + 1)))


solve()

Submission status: Runtime Error

Solution code:
MOD = 998244353


def solve(s, k):
    one_count = []
    ones = 0
    for st in s:
        if st == "1":
            ones += 1
        else:
            one_count.append(ones)
            ones = 0
    one_count.append(ones)
    m = len(one_count)
    dp = [[[0] * 300 for _ in range(300)] for __ in range(m + 1)]
    dp[0][0][0] = 1
    for i in range(m):
        c = one_count[i]
        for j in range(300):
            for p in range(300):
                dp[i][j][p] %= MOD
                for q in range(300 - max(j, p)):
                    dp[i + 1][j + q][p + q] += dp[i][j][p]
                for q in range(-c, 0):
                    dp[i + 1][j + q][p] += dp[i][j][p]

    # print(dp)
    res = sum([dp[m][0][p] for p in range(k + 1)])
    # print(res)
    return res % MOD


def main():
    s, k_ = input().split()
    k = int(k_)
    res = solve(s, k)
    print(res)


def test():
    assert solve("0101", 1) == 4
    assert solve("01100110", 2) == 14
    assert solve("1101010010101101110111100011011111011000111101110101010010101010101", 20) == 113434815


if __name__ == "__main__":
    test()
    main()

Submission status: Runtime Error

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

S,K=input().split()
K=int(K)
mod=998244353

LEN=len(S)

ONES=[]
Z=0
for s in S:
    if s=="0":
        Z+=1
    else:
        ONES.append(Z)

O=len(ONES)
Z=ONES[-1]

DP=[[0]*(O+1) for i in range(O+1)]
DP[0][0]=1

# DP[i][j]で, i個石を動かし、j個石が残っているときの場合の数

from collections import Counter
C=Counter(ONES)

for numb in range(Z,-1,-1):
    #print(DP)
    c=C[numb]

    NDP=[[0]*(O+1) for i in range(O+1)]

    for i in range(O+1):        
        for j in range(O+1):
            if DP[i][j]==0:
                continue
            for oku in range(c+j+1):
                if i+max(0,oku-c)<=O and 0<=c+j-oku<=O:
                    NDP[i+max(0,oku-c)][c+j-oku]+=DP[i][j]
    DP=NDP

ANS=0
for i in range(min(O,K)+1):
    ANS+=DP[i][0]

print(ANS%mod)

Submission status: Runtime Error

Solution code:
s, k = input().split()
mod = 998244353
k = int(k)
n = len(s)
z = s.count("0")
S = [0] * (z+1)
ind = 0
for i in range(n):
    if s[i] == "0":
        ind += 1
    else:
        S[ind] += 1
# print(S)

D = [[0] * (k+1) for i in range(k+1)]
D[0][0] = 1
for ii in range(z+1):
    
    D0 = [[0] * (k+1) for i in range(k+1)]
    for j in range(k):
        if j+1 < k+1:
            for l in range(k+1):
                D0[j+1][l] = (D0[j+1][l] + D[j][l]) % mod
        if S[len(S)-1-ii] + j + 1 < k+1:
            # print("ind",S[len(S)-1-ii] + j + 1)
            for l in range(k+1):
                D0[S[len(S)-1-ii] + j + 1][l] = (D0[S[len(S)-1-ii] + j + 1][l] - D[j][l]) % mod

    for j in range(1, k+1):
        for l in range(k+1):
            D0[j][l] = (D0[j][l] + D0[j-1][l]) % mod

    D1 = [D[i][:] for i in range(k+1)]
    # D1[0][0] = 0
    for i in range(1, k+1):
        r = i-1
        c = 1
        while 0 <= r < k+1 and 0 <= c < k+1:
            # print("r c",r,c)
            D1[r][c] = (D1[r][c] + D1[r+1][c-1]) % mod
            r -= 1
            c += 1
    for i in range(1, k):
        r = k-1
        c = i+1
        while 0 <= r < k+1 and 0 <= c < k+1:
            D1[r][c] = (D1[r][c] + D1[r+1][c-1]) % mod
            r -= 1
            c += 1

    # for i in range(k):
    #     D1[i][0] = 0
    # for i in range(k):
    #     D1[k][i] = 0

    # print(D,D0,D1)
    for i in range(k+1):
        for j in range(k+1):
            D[i][j] = (D0[i][j] + D1[i][j]) % mod

# print(sum(D[i][i] for i in range(k+1)))
print(sum(D[0]) % mod)
# print(D)

Submission status: Runtime Error

Solution code:
a=input()
b=a[2:]
ans=0
for j in range(1):
 for i in range(len(a)):
  c=b[i:]+a[j]+b[b+1:]
  ans+=1
  print(c)

Submission status: Runtime Error

Solution code:
S, K = input().split()
K = int(K)

def func(s, k):
  output = [s]
  for i in range(len(s)):
    for j in range(i+1, len(s)):
      if s[i] == '0' and s[j] == '1':
        temp = s[:i] + s[j] + s[i:j] + s[j+1:]
        output.append(temp)
  output = list(set(output))
  if k == 1:
    return output
  
  output2 = output
  for i in range(len(output)):
  	output2 = output2 + func(output[i], k-1)

  return output2

print(len(set(func(S, K))) % 998244353)

Submission status: Runtime Error

Solution code:
S, K = input().split()
K = int(K)

def func(s, k):
  if k == 0:
    return [s]
  else:
    output = [s]
    for i in range(len(s)):
      for j in range(i+1, len(s)):
        if s[i] == '0' and s[j] == '1':
          temp = s[:i] + s[j] + s[i:j] + s[j+1:]
          output.append(temp)
  output = list(set(output))
  output2 = output
  for i in range(len(output)):
  	output2 = output2 + func(output[i], k-1)

  return output2

print(len(set(func(S, K))) % 998244353)

Submission status: Runtime Error

Solution code:
S, K = list(map(int, input().split()))

def func(s, k):
  if k == 0:
    return [s]
  else:
    output = [s]
    for i in range(len(s)):
      for j in range(i+1, len(s)):
        if s[i] == '0' and s[j] == '1':
          temp = s[:i] + s[j] + s[i:j] + s[j+1:]
          output.append(temp)
  output = list(set(output))
  output2 = output
  for i in range(len(output)):
  	output2 = output2 + func(output[i], k-1)

  return output2

print(len(set(func(S, K))) % 998244353)

Submission status: Runtime Error

Solution code:
S, K = list(map(int, input().split()))

def func(s, k):
  if k == 0:
    return [s]
  else:
    output = [s]
    for i in range(len(s)):
      for j in range(i+1, len(s)):
        if s[i] == '0' and s[j] == '1':
          temp = s[:i] + s[j] + s[i:j] + s[j+1:]
          output.append(temp)
          output2 = output
          for i in range(len(output)):
            output2 = output2 + func(output[i], k-1)

  return output2

print(len(set(func(S, K))) % 998244353)