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

Solution code:
sk = input().split()
s = sk[0]
K = int(sk[1])
mod = 998244353

x = [0]
for si in s:
    if(si=='0'):
        x.append(0)
    else:
        x[-1] += 1

while(x):
    if(x[-1] == 0):
        x.pop()
    else:
        break
x = x[::-1]
len_x = len(x)
ones = min(K,sum(x))
dp = [[] for _ in range(len_x+1)]

for i in range(len_x+1):
    dp[i] = [[0] * (ones+1) for _ in range(ones+1)]

dp[0][0][0] = 1
for i,xi in enumerate(x):
    cumsum_y = [[0] * (ones+2) for _ in range(ones+2)]
    cumsum_xy = [[0] * (ones+2) for _ in range(ones+2)]

    for j in range(ones+1):
        for k in range(ones+1):
            cumsum_y[j+1][k+1] = (cumsum_y[j][k+1] + dp[i][j][k])%mod
            cumsum_xy[j+1][k+1] = (cumsum_xy[j][k] + dp[i][j][k])%mod

    for j in range(ones+1):
        for k in range(j,ones+1):
            dp[i+1][j][k] += cumsum_y[k+1][k+1] - cumsum_y[j][k+1]
            dp[i+1][j][k] += cumsum_xy[j][k] - cumsum_xy[max(0,j-xi)][max(0,j-xi) + k-j]
            dp[i+1][j][k] %= mod

ans = 0
for k in range(ones+1):
    ans += dp[-1][0][k]
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
S,Kstring = input().split()
K = int(Kstring)
lastZero = -1
segment = []
MOD = 998244353
N = len(S)

for i in range(N):
    if S[i] == '0':
        segment.append(i - lastZero - 1)
        lastZero = i

segment.append(N - 1 - lastZero)
M = len(segment)
No1 = N + 1 - M

partialSumSegment = []
for i in range(M):
    if partialSumSegment:
        partialSumSegment.append(segment[i] + partialSumSegment[-1])
    else:
        partialSumSegment.append(segment[i])

DP = []
DPSum = [] # Sum of DP i,j,k ~ i,j,a
for i in range(M):
    DP.append([])
    DPSum.append([])
    for j in range(No1 + 2):
        DP[i].append([])
        DPSum[i].append([])
        for k in range(No1 + 2):
            DP[i][j].append(0)
            DPSum[i][j].append(0)

# Initialize on the last segment

for j in range(No1 - partialSumSegment[M-2] + 1):
    DP[M-1][j][partialSumSegment[M-2] + j] = 1
for j in range(No1 - partialSumSegment[M-2] + 1):
    for k in range(partialSumSegment[M-2] + j,-1,-1):
        DPSum[M-1][j][k] = DPSum[M-1][j][k+1] + DP[M-1][j][k]

for i in range(M-2,-1,-1):
    for j in range(No1 + 1):
        Kmin = partialSumSegment[i-1]
        if i == 0:
            Kmin = 0
        for k in range(No1, Kmin - 1, -1):
            DPCur = 0
            for l in range(1,segment[i] + 1):
                if j >= l and k + segment[i] - l <= No1 + 1:
                    DPCur += DP[i + 1][j - l][k + segment[i] - l]
            if k + segment[i] <= No1:
                DPCur += DPSum[i + 1][j][k + segment[i]]
            DP[i][j][k] = DPCur % MOD
            DPSum[i][j][k] = (DPSum[i][j][k+1] + DP[i][j][k]) % MOD 

# print(DP)
# print(DPSum)

AnsSum = 0
for j in range(min(K,No1) + 1):
    AnsSum += DP[0][j][0]

if M == 1:
    print(1)
else:
    print(AnsSum % MOD)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 998244353
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    s,K=input().split()
    K=int(K)
    
    l=len(s)
    if K>l:
        K=l
    sep=[]
    count=0
    for i in range(l):
        if s[i]=="1": count+=1
        else:
            sep.append(count)
            count=0

    sep.append(count)

    dp=[[[0]*(l+1) for _ in range(K+1)] for _ in range(len(sep))]
    #dp[i][j][k] 末尾からi番目の領域、j個の0をストック,k回の操作
    dp[0][0][0]=1
    for i in range(1,min(sep[-1]+1,K+1)):
        dp[0][i][i]=1
    dp20=[[0]*(l+1) for _ in range(K+1)]
    for i in range(1,len(sep)):
        ori=sep[-1-i]
        dp2=deepcopy(dp20)
        for k in range(K+1):
            dp[i][k][-1]=dp[i-1][k][-1]
            for j in range(1,l+1):
                dp[i][k][-1-j]=(dp[i][k][-j]+dp[i-1][k][-1-j])%mod
                if k==0 or j==0: continue
                
                dp2[k][j]=(dp2[k-1][j-1]+dp[i-1][k-1][j-1])%mod
                if j>ori and k>ori:
                    dp2[k][j]-=dp[i-1][k-ori-1][j-ori-1]
                    dp2[k][j]%=mod
        for k in range(K+1):
            for j in range(1,l+1):
                dp[i][k][j]=(dp[i][k][j]+dp2[k][j])%mod
    

    ans=0
    for k in range(K+1):
        ans+=dp[-1][k][0]
        ans%=mod
    print(ans)
    #print(dp)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import groupby
import numpy as np


def solve(s, k):
    sgrp = [len(list(itr)) for c, itr in groupby(s)]
    if len(sgrp) == 1:
        return 1

    one_bucket = []
    MOD = 998244353

    if s[0] == '1':
        one_bucket.append(sgrp[0])
        sgrp = sgrp[1:]
    else:
        one_bucket.append(0)

    cur = 0
    for l in sgrp:
        if cur == 0:
            one_bucket.extend([0] * (l - 1))
        else:
            one_bucket.append(l)
        cur ^= 1

    k = min(k, sum(one_bucket))
    dp = np.zeros((k + 1, k + 1), dtype=np.int64)
    dp[0, 0] = 1

    for i, c in enumerate(one_bucket):
        ndp = np.add.accumulate(dp, axis=0)
        if c > 0:
            for j in range(1, c + 1):
                ndp[:, j:] += dp[:, :-j]
            ndp = np.tril(ndp)
        dp = ndp % MOD

    return np.diag(dp).sum() % MOD


s, k = input().split()
k = int(k)

print(solve(s, k))

Submission status: Accepted

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

L = []
o = "0"
z = "1"

if S[0] == o:
  L.append(0)
  cnt = 0
else:
  cnt = 1

for i in range(1, len(S)):
  if S[i] == o:
    L.append(cnt)
    cnt = 0
  else:
    cnt += 1
if cnt != 0:
  L.append(cnt)

N = len(L) 
s = sum(L)
M = min(s, K) + 1
DP = [[[0] * M for _ in range(M)] for _ in range(N)]

s -= L[0]
for i in range(min(s, K) + 1):
  DP[0][0][i] = 1

for i in range(1, N):
  s -= L[i]
  t = min(K, s) + 1
  for j in range(M):
    c = 0
    for k in range(M):
      c = (c + DP[i - 1][j][k]) % MOD
      if k - t >= 0:
        c -= DP[i - 1][j][k - t]
        if c < 0: c += MOD
      DP[i][j][k] = c
  t = min(K, L[i])
  for k in range(M):
    c = 0
    for j in range(k + 1):
      DP[i][j][k] = (DP[i][j][k] + c) % MOD
      c = (c + DP[i - 1][j][k]) % MOD
      if j - t >= 0:
        c -= DP[i - 1][j - t][k]
        if c < 0: c += MOD

ans = 0
for i in range(M):
  ans = (ans + DP[-1][i][i]) % MOD

print(ans)

Submission status: Accepted

Solution code:
mod = 998244353
S, K = input().split()
a = [len(x) for x in S.split("0")]
K = min(int(K), sum(a)+1)

# f[i][j][k] : 右からi個目の区間まで見て、これまでにj個の1をpick upして、そのうちk個の置き場所が確定しているような操作を行った後の"状態数"
# ans -> f[len(a)][0][0] + f[len(a)][1][1] + ... + f[len(a)][K][K]


def solve_naive():  # TLE解
    f = [[[0 for k in range(K+1)] for j in range(K+1)]
         for i in range(len(a)+1)]

    for i in range(len(a)+1):
        if i == 0:
            # 区間を一つも見ていないので、1を選ぶことができない
            f[i][0][0] = 1
        else:
            for j in range(K+1):
                for k in range(j+1):
                    # 1. 右からi番目の区間a[-i]では何もしない（i.e. a[-i]から1を取らないし、持ってる1をa[-i]に置かない）
                    f[i][j][k] += f[i-1][j][k]
                    f[i][j][k] %= mod

                    # 2. a[-i]に1をいくつか置く
                    for num in range(1, j-k+1):
                        if k + num > K:
                            break
                        f[i][j][k+num] += f[i-1][j][k]  # a[-i]に1をnum個置く
                        f[i][j][k+num] %= mod

                    # 3. a[-i]から1をいくつか取る。
                    # 注: a[-1]に1を「置く」と「取る」を両方することは考えなくてよい。より少ない回数の操作で同じ状態が実現されるので。
                    for num in range(1, a[-i]+1):
                        if j + num > K:
                            break
                        f[i][j+num][k] += f[i-1][j][k]  # a[-i]から1をnum個取る
                        f[i][j+num][k] %= mod
    ans = 0
    for num in range(K+1):
        ans += f[len(a)][num][num]
        ans %= mod
    return ans


def solve():
    f = [[[0 for k in range(K+1)] for j in range(K+1)]
         for i in range(len(a)+1)]

    for i in range(len(a)+1):
        if i == 0:
            # 区間を一つも見ていないので、1を選ぶことができない
            f[i][0][0] = 1
        else:
            for j in range(K+1):
                cum2 = 0
                for k in range(j+1):
                    # 1. 右からi番目の区間a[-i]では何もしない（i.e. a[-i]から1を取らないし、持ってる1をa[-i]に置かない）
                    f[i][j][k] += f[i-1][j][k]
                    f[i][j][k] %= mod

                    # 2. a[-i]に1をいくつか置く
                    # f[i][j][k] += f[i-1][j][0] (a[-i]にk個置く) + f[i-1][j][1]+ ... + f[i-1][j][k-1] (a[-i]に1個置く)
                    f[i][j][k] += cum2
                    f[i][j][k] %= mod
                    cum2 += f[i-1][j][k]

            for k in range(K+1):
                cum3 = 0
                for j in range(k, K+1):
                    # 3. a[-i]から1をいくつか取る。
                    # 注: a[-1]に1を「置く」と「取る」を両方することは考えなくてよい。より少ない回数の操作で同じ状態が実現されるので。
                    # f[i][j][k] += f[i-1][k][k] (a[-i]からj-k個取る) + f[i-1][k+1][k] + .... + f[i-1][j-1][k] (a[-i]から1個取る)
                    if j < a[-i]:
                        f[i][j][k] += cum3
                        f[i][j][k] %= mod
                        cum3 += f[i-1][j][k]
                    else:
                        f[i][j][k] += cum3
                        f[i][j][k] %= mod
                        cum3 += f[i-1][j][k] - f[i-1][j-a[-i]][k]
    ans = 0
    for num in range(K+1):
        ans += f[len(a)][num][num]
        ans %= mod
    return ans


print(solve_naive())

Submission status: Accepted

Solution code:
mod = 998244353
S, K = input().split()
a = [len(x) for x in S.split("0")]
K = min(int(K), sum(a)+1)

# f[i][j][k] : 右からi個目の区間まで見て、これまでにj個の1をpick upして、そのうちk個の置き場所が確定しているような操作を行った後の"状態数"
# ans -> f[len(a)][0][0] + f[len(a)][1][1] + ... + f[len(a)][K][K]


def solve_naive():  # TLE解
    f = [[[0 for k in range(K+1)] for j in range(K+1)]
         for i in range(len(a)+1)]

    for i in range(len(a)+1):
        if i == 0:
            # 区間を一つも見ていないので、1を選ぶことができない
            f[i][0][0] = 1
        else:
            for j in range(K+1):
                for k in range(j+1):
                    # 1. 右からi番目の区間a[-i]では何もしない（i.e. a[-i]から1を取らないし、持ってる1をa[-i]に置かない）
                    f[i][j][k] += f[i-1][j][k]
                    f[i][j][k] %= mod

                    # 2. a[-i]に1をいくつか置く
                    for num in range(1, j-k+1):
                        if k + num > K:
                            break
                        f[i][j][k+num] += f[i-1][j][k]  # a[-i]に1をnum個置く
                        f[i][j][k+num] %= mod

                    # 3. a[-i]から1をいくつか取る。
                    # 注: a[-1]に1を「置く」と「取る」を両方することは考えなくてよい。より少ない回数の操作で同じ状態が実現されるので。
                    for num in range(1, a[-i]+1):
                        if j + num > K:
                            break
                        f[i][j+num][k] += f[i-1][j][k]  # a[-i]から1をnum個取る
                        f[i][j+num][k] %= mod
    ans = 0
    for num in range(K+1):
        ans += f[len(a)][num][num]
        ans %= mod
    return ans


def solve():
    f = [[[0 for k in range(K+1)] for j in range(K+1)]
         for i in range(len(a)+1)]

    for i in range(len(a)+1):
        if i == 0:
            # 区間を一つも見ていないので、1を選ぶことができない
            f[i][0][0] = 1
        else:
            for j in range(K+1):
                cum2 = 0
                for k in range(j+1):
                    # 1. 右からi番目の区間a[-i]では何もしない（i.e. a[-i]から1を取らないし、持ってる1をa[-i]に置かない）
                    f[i][j][k] += f[i-1][j][k]
                    f[i][j][k] %= mod

                    # 2. a[-i]に1をいくつか置く
                    # f[i][j][k] += f[i-1][j][0] (a[-i]にk個置く) + f[i-1][j][1]+ ... + f[i-1][j][k-1] (a[-i]に1個置く)
                    f[i][j][k] += cum2
                    f[i][j][k] %= mod
                    cum2 += f[i-1][j][k]

            for k in range(K+1):
                cum3 = 0
                for j in range(k, K+1):
                    # 3. a[-i]から1をいくつか取る。
                    # 注: a[-1]に1を「置く」と「取る」を両方することは考えなくてよい。より少ない回数の操作で同じ状態が実現されるので。
                    # f[i][j][k] += f[i-1][k][k] (a[-i]からj-k個取る) + f[i-1][k+1][k] + .... + f[i-1][j-1][k] (a[-i]から1個取る)
                    if j < a[-i]:
                        f[i][j][k] += cum3
                        f[i][j][k] %= mod
                        cum3 += f[i-1][j][k]
                    else:
                        f[i][j][k] += cum3
                        f[i][j][k] %= mod
                        cum3 += f[i-1][j][k] - f[i-1][j-a[-i]][k]
    ans = 0
    for num in range(K+1):
        ans += f[len(a)][num][num]
        ans %= mod
    return ans


print(solve())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 998244353
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
S,K = SL()
K = int(K)

data = []
ones = 0
count = 0
for s in S:
  if s == "1":
    count += 1
    ones += 1
  else:
    data.append(count)
    count = 0
data.append(count)
data = data[::-1]
N = len(data)
#print(data)
K = min(K,ones)

dp = [[[0 for j in range(K+1)] for k in range(K+1)] for i in range(N)]
for i in range(N):
  dp[i][0][0] = 1
for k in range(min(data[0]+1,K+1)):
  dp[0][k][k] = 1
#print(dp[0])
for i in range(1,N):
  for k in range(K+1):   
    for j in range(K+1)[::-1]:
      if j == K:
        dp[i][k][j] = dp[i-1][k][j]
        dp[i][k][j] %= MOD
      else:
        dp[i][k][j] = dp[i-1][k][j] + dp[i][k][j+1]
        dp[i][k][j] %= MOD
  a = data[i]
  if a:
    for k in range(K):
      q = deque([dp[i-1][k][0]])
      temp = dp[i-1][k][0]
      for j in range(1,K+1):
        #print(i,k,q)
        if k+j > K: break
        dp[i][k+j][j] += temp
        dp[i][k+j][j] %= MOD
        q.append(dp[i-1][k+j][j])
        temp += dp[i-1][k+j][j]
        if len(q) > a:
          temp -= q.popleft()
        temp %= MOD
  #print(dp[i])
      
ans = 0
for k in range(K+1):
  ans += dp[-1][k][0]
  ans %= MOD
  
print(ans)

Submission status: Accepted

Solution code:
def main():
    mod = 998244353
    s, k = input().split()
    k, n, o, cnt, z, zero_list = int(k), len(s), s.count("1")+1, 0, 0, []
    for i in range(n):
        if s[i] == "0":
            zero_list.append(cnt)
            cnt = 0
        else:
            cnt += 1
    m = min(o, k+1)

    dp = [[0]*m for _ in [0]*o]
    dp[0][0] = 1

    for i in zero_list:
        dp2 = [[0]*m for _ in [0]*o]
        dp3 = [[0] for _ in [0]*o]
        for x in range(o):
            t = 0
            for y in range(min(m, o-x)):
                t = (t+dp[x+y][y]) % mod
                dp3[x].append(t)
        dp4 = [[0]*m for _ in [0]*o]
        for y in range(m):
            t = dp[0][y]
            for x in range(1, o):
                dp4[x-1][y] = t
                t = (t+dp[x][y]) % mod
            dp4[o-1][y] = t
        for j in range(z+i, o):
            for x in range(min(j-i+1, m)):
                dp2[j][x] = (dp2[j][x]+dp3[j-x-i][min(o, x+1)]) % mod
            for p in range(m):
                dp2[j][p] = (dp2[j][p]+dp4[j][p]-dp4[max(j-i, p-1)][p]) % mod
        z += i
        dp = dp2
    print(sum([sum(i) for i in dp]) % mod)


main()

Submission status: Accepted

Solution code:
S,K=input().split()
K=int(K)
K=min(K,300)
mod=998244353
a=[]
val=0
for i in range(len(S)):
    if S[i]=="0":
        a.append(val)
        val=0
    else:
        val+=1

if val!=0:
    a.append(val)
m=len(a)
K=min(sum(a),K)

b=[a[i] for i in range(m)]
c=[a[i] for i in range(m)]
for i in range(1,m):
    b[i]+=b[i-1]
b=[0]+b
for i in range(m-2,-1,-1):
    c[i]+=c[i+1]

dp=[[0 for i in range(K+1)] for j in range(K+1)]
plus=[[0 for j in range(K+1)] for k in range(K+1)]
minus=[[0 for j in range(K+1)] for k in range(K+1)]

for j in range(K+1):
    dp[j][j]=1
    plus[j][j]=1
    minus[j][j]=1

for k in range(K+1):
    for j in range(1,K+1):
        plus[j][k]+=plus[j-1][k]

for j in range(K+1):
    for k in range(1,K+1):
        minus[j][k]+=minus[j][k-1]

for i in range(m-1,-1,-1):
    ndp=[[0 for j in range(K+1)] for k in range(K+1)]
    for k in range(min(b[i],K)+1):
        for j in range(min(K,k+c[i])+1):
            M=max(k-j,-a[i])
            if max(0,M)+j==0:
                ndp[j][k]+=plus[K][k]
            else:
                ndp[j][k]+=plus[K][k]-plus[(max(0,M))+j-1][k]
            if min(K-k,-M)>0:
                ndp[j][k]+=minus[j][k+min(K-k,-M)]-minus[j][k]
            ndp[j][k]%=mod
    dp=ndp
    for j in range(K+1):
        for k in range(K+1):
            plus[j][k]=ndp[j][k]
            minus[j][k]=ndp[j][k]

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

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


print(dp[0][0])

Submission status: Accepted

Solution code:
S,K=input().split()
K=int(K)
K=min(K,300)
mod=998244353
a=[]
val=0
for i in range(len(S)):
    if S[i]=="0":
        a.append(val)
        val=0
    else:
        val+=1

if val!=0:
    a.append(val)
m=len(a)
K=min(sum(a),K)

dp=[[0 for i in range(K+1)] for j in range(K+1)]

for j in range(K+1):
    dp[j][j]=1

b=[a[i] for i in range(m)]
c=[a[i] for i in range(m)]
for i in range(1,m):
    b[i]+=b[i-1]
b=[0]+b
for i in range(m-2,-1,-1):
    c[i]+=c[i+1]
for i in range(m-1,-1,-1):
    ndp=[[0 for j in range(K+1)] for k in range(K+1)]
    for k in range(min(b[i],K)+1):
        for j in range(min(K,k+c[i])+1):
            M=max(k-j,-a[i])
            for l in range(max(0,M),K-j+1):
                ndp[j][k]=(ndp[j][k]+dp[j+l][k])%mod
            for l in range(1,min(K-k,-M)+1):
                ndp[j][k]=(ndp[j][k]+dp[j][k+l])%mod
    dp=ndp

print(dp[0][0])

Submission status: Accepted

Solution code:
mod = 998244353
S,K = input().split()
a = []
c = 0
for i in range(len(S)):
    if S[i]=='0':
        a.append(c)
        c = 0
    else:
        c += 1
if S[-1]=='1':
    a.append(c)
a = a[::-1]
K = min(sum(a),int(K))
N = len(a)
dp = [[[0]*(K+1) for _ in range(K+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for j in range(K+1):
        for k in range(j+1):
            for l in range(a[i]+1):
                if j+l>K:
                    break
                dp[i+1][j+l][k+l] += dp[i][j][k]
                dp[i+1][j+l][k+l] %= mod
            for l in range(1,k+1):
                dp[i+1][j][k-l] += dp[i][j][k]
                dp[i+1][j][k-l] %= mod
                
ans = 0
for k in range(K+1):
    ans += dp[N][k][0]
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
S,K=input().split()
K=int(K)
K=min(K,300)
mod=998244353
a=[]
val=0
for i in range(len(S)):
    if S[i]=="0":
        a.append(val)
        val=0
    else:
        val+=1

if val!=0:
    a.append(val)
m=len(a)
K=min(sum(a),K)

dp=[[0 for i in range(K+1)] for j in range(K+1)]

for j in range(K+1):
    dp[j][j]=1

b=[a[i] for i in range(m)]
c=[a[i] for i in range(m)]
for i in range(1,m):
    b[i]+=b[i-1]
b=[0]+b
for i in range(m-2,-1,-1):
    c[i]+=c[i+1]
for i in range(m-1,-1,-1):
    ndp=[[0 for j in range(K+1)] for k in range(K+1)]
    for k in range(min(b[i],K)+1):
        for j in range(min(K,k+c[i])+1):
            M=max(k-j,-a[i])
            ndp[j][k]=sum(dp[j+l][k] for l in range(max(0,M),K-j+1))+sum(dp[j][k+l] for l in range(1,min(K-k,-M)+1))
            ndp[j][k]%=mod
    dp=ndp

print(dp[0][0])

Submission status: Accepted

Solution code:
S,K=input().split()
K=int(K)
K=min(K,300)
mod=998244353
a=[]
val=0
for i in range(len(S)):
    if S[i]=="0":
        a.append(val)
        val=0
    else:
        val+=1

if val!=0:
    a.append(val)
m=len(a)
K=min(sum(a),K)

dp=[[[0 for i in range(K+1)] for j in range(K+1)] for k in range(m+1)]

for j in range(K+1):
    dp[m][j][j]=1

b=[a[i] for i in range(m)]
c=[a[i] for i in range(m)]
for i in range(1,m):
    b[i]+=b[i-1]
b=[0]+b
for i in range(m-2,-1,-1):
    c[i]+=c[i+1]
for i in range(m-1,-1,-1):
    for k in range(min(b[i],K)+1):
        for j in range(min(K,k+c[i])+1):
            M=max(k-j,-a[i])
            dp[i][j][k]=sum(dp[i+1][j+l][k] for l in range(max(0,M),K-j+1))+sum(dp[i+1][j][k+l] for l in range(1,min(K-k,-M)+1))
            dp[i][j][k]%=mod

print(dp[0][0][0])

Submission status: Accepted

Solution code:
S,K=input().split()
K=int(K)
K=min(K,300)
mod=998244353
a=[]
val=0
for i in range(len(S)):
    if S[i]=="0":
        a.append(val)
        val=0
    else:
        val+=1

if val!=0:
    a.append(val)
m=len(a)
K=min(sum(a),K)

dp=[[[0 for i in range(K+1)] for j in range(K+1)] for k in range(m+1)]

for j in range(K+1):
    dp[m][j][j]=1

b=[a[i] for i in range(m)]
c=[a[i] for i in range(m)]
for i in range(1,m):
    b[i]+=b[i-1]
b=[0]+b
for i in range(m-2,-1,-1):
    c[i]+=c[i+1]
for i in range(m-1,-1,-1):
    for j in range(K+1):
        for k in range(min(b[i],K)+1):
            M=max(k-j,-a[i])
            dp[i][j][k]=sum(dp[i+1][j+l][k] for l in range(max(0,M),K-j+1))+sum(dp[i+1][j][k+l] for l in range(1,min(K-k,-M)+1))
            dp[i][j][k]%=mod

print(dp[0][0][0])

Submission status: Accepted

Solution code:
s,k = input().split()
mod = 998244353
k = int(k)
k = min(300,k)
raw = [0]
l = len(s)
for i in range(l):
  if s[i] == '0':
    raw.append(0)
  else:
    raw[-1] += 1
#print(raw)
now = [[0 for _ in range(k+1)] for _ in range(k+1)]
l = len(raw)
raw.reverse()
#print(raw)
now[0][0] = 1
for x in raw:
  last = now[:]
  now = []
  for i in range(k+1):
    use = last[i][:]
    use.reverse()
    cum = []
    for j in range(k+1):
      if cum:
        cum.append(cum[-1]+use[j])
        cum[-1] %= mod
      else:
        cum = [use[0]]
    cum.reverse()
    now.append(cum)
    #print(cum)
  #print('#')
  cum2 = []
  for i in range(k+1):
    cum = [0 for _ in range(i)]
    cum.append(last[i][0])
    #print('%',cum)
    for l in range(i+1,k+1):
      cum.append(cum[-1]+last[l][l-i])
    #print(cum)
    cum2.append(cum)
  for i in range(k+1):
    for j in range(k+1):
      if j > i:
        pass
      now[i][j] += cum2[i-j][i]
      if i - x - 1 >= 0:
        now[i][j] -= cum2[i-j][i-x-1]
      now[i][j] %= mod
  for i in range(k+1):
    for j in range(k+1):
      now[i][j] -= last[i][j]
      now[i][j] %= mod
  #print(now)
  #print('##')
        
  #print(now)
#print(now)
ans = 0
for i in range(k+1):
  ans += now[i][0]
print(ans%mod)

Submission status: Accepted

Solution code:
S,K = input().split()
A = list(map(len,S.split("0")))
A[0] = 0
A.append(0)
N = len(A)
K = int(K)
K = min(K,S.count("1"))

MOD = 998244353

dp = [[[0]*(K+1) for _ in [0]*(K+1)] for _ in [0]*N]
dp[-1][0][0] = 1

for i in range(1,N):
    i = N-1-i
    for k in range(K+1):
        for n in range(K+1):
            dp[i][k][n] = sum(dp[i+1][k][n:])%MOD
            for a in range(1,A[i]+1):
                if k-a < 0 or n-a < 0: break
                dp[i][k][n] += dp[i+1][k-a][n-a]
                dp[i][k][n] %= MOD
ans = sum(dp[0][k][0] for k in range(K+1))
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#a,b,c,d = map(int,readline().split())
s,k = readline().split()


a = [len(i) for i in s.split("0")]
while a and a[-1] == 0: a.pop()

if not a:
    print(1)
    exit()

MOD = 998244353

M = sum(a)+1
k = min(int(k),M)


dp = [[0]*M for _ in range(k+1)] # j 使って（上限 k）、l 余ってる
dp[0][0] = 1

#print(a)
for ai in a[::-1]:
    ndp = [[0]*M for _ in range(k+1)] # j 使って（上限 k）、l 余ってる
    for j in range(k+1):
        for l in range(M):
            if dp[j][l]:
                for ll in range(l):
                    ndp[j][ll] += dp[j][l]
                    ndp[j][ll] %= MOD

                V = min(M-l,k-j+1,ai+1)
                for i in range(V):
                    #if j+i > k: break
                    ndp[j+i][l+i] += dp[j][l]
                    ndp[j+i][l+i] %= MOD
    
    dp = ndp
    #print(dp)

ans = 0
for jj in range(k+1):
    ans += dp[jj][0]

print(ans%MOD)

Submission status: Accepted

Solution code:
def main():
    mod = 998244353
    s, k = input().split()
    k, n, one, cnt, z, zero_list = int(k), len(s), s.count("1")+1, 0, 0, []
    for i in range(n):
        if s[i] == "0":
            zero_list.append(cnt)
            cnt = 0
        else:
            cnt += 1
    mm = min(one-1, k)

    dp = [[0]*(mm+1) for _ in [0]*one]
    dp[0][0] = 1

    for i in zero_list:
        dp2 = [[0]*(mm+1) for _ in [0]*one]
        for j in range(one):
            for l in range(max(z+i-j, 0), one-j):
                ml = max(l-i, 0)
                for p in range(min(j, mm-ml)+1):
                    dp2[j+l][p+ml] = (dp2[j+l][p+ml]+dp[j][p]) % mod
        z += i
        dp = dp2
    print(sum([sum(i) for i in dp]) % mod)


main()