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: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=1):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.node_size=len(ls)+1
                self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.node_size=int(input())
        else:
            self.node_size=inp_size
        self.edges,_=GI(self.node_size,self.node_size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.node_size=len(ls)+1
        self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def parent(self,x):
        return self.dfs(0,func=lambda pr,prv,nx,dist:pr,root_v=-1)
 
    def topological_sort(self,x):  # return topological sort of the tree
        tps=[]
        q=deque([x])
        v=[None]*self.node_size
        v[x]=0
        while q:
            c=q.popleft()
            tps.append(c)
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=0
        return tps
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.node_size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.node_size
        self.ETout=[-1]*self.node_size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        #self.st=SegTree(self.node_size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
    def __str__(self):
        return  str(self.edges)
 
    def show(self):
        if all([all([d==1 for nd,d in e]) for e in self.edges]):
            print( [[nd for nd,d in e] for e in self.edges] )
        else:
            print(self)

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    # return boundary index of r such that func({table[i]} =< x , i in [pos,r]
    def right_bound(self,pos,x):
        k=(self.size-pos).bit_length()
        for j in range(k)[::-1]:
            nx=pos+(1<<j)
            if nx<n and self.query(pos,nx+1)<=x:
                pos+=(1<<j)
        return pos
    
    # return boundary index of l such that func({table[i]} =< x , i in [l,pos]
    def left_bound(self,pos,x):
        k=pos.bit_length()
        for j in range(k)[::-1]:
            nx=pos-(1<<j)
            if 0<=nx and self.query(nx,pos+1)<=x:
                pos-=(1<<j)
        return pos
 
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)


show_flg=False
show_flg=True


ans=0
mo=998244353

s,k=input().split()
K=int(k)
c=0
t=[]
for i in s+'0':
    if i=='1':
        c+=1
    else:
        t+=[c]
        c=0
t=t[::-1]
one=sum(t)
ans=t
n=len(t)

D=300
m=min(K+1,D)

dp=[[[0]*(m+1) for i in range(one+1)] for i in range(n+1)]
dp[0][0][0]=1

for i in range(n)[::-1]:
    for x in range(m+1):
        if 0<=t[i]-x<=one and 0<=K+x<=m:
            dp[i+1][t[i]-x][K+x]+=dp[i][x][K]

print(ans)

show(t,one)
show(dp)

exit()        
for i in dp:
    show(*i)
#show(sum(dp))

Submission status: Wrong Answer

Solution code:
s,k = input().split()
mod = 998244353
k = int(k)
k = min(170,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 = [[0 for _ in range(k+1)] for _ in range(k+1)]
  for i in range(k+1):
    for j in range(k+1):
      for mag in range(x+1):
        if mag + i > k or mag + j > k:
          continue
        now[i+mag][j+mag] += last[i][j]
        now[i+mag][j+mag] %= mod
      for dim in range(j):
        now[i][dim] += last[i][j]
        now[i][dim] %= mod
  #print(now)
#print(now)
ans = 0
for i in range(k+1):
  ans += now[i][0]
print(ans%mod)

Submission status: Wrong Answer

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


print(sum(dp[:min(kk+1,200*200+1)]))

Submission status: Wrong Answer

Solution code:
s,k = input().split()
mod = 998244353
k = int(k)
k = min(180,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 = [[0 for _ in range(k+1)] for _ in range(k+1)]
  for i in range(k+1):
    for j in range(k+1):
      for mag in range(x+1):
        if mag + i > k or mag + j > k:
          continue
        now[i+mag][j+mag] += last[i][j]
        now[i+mag][j+mag] %= mod
      for dim in range(j):
        now[i][dim] += last[i][j]
        now[i][dim] %= mod
  #print(now)
#print(now)
ans = 0
for i in range(k+1):
  ans += now[i][0]
print(ans%mod)

Submission status: Wrong Answer

Solution code:
s,k = input().split()
K = int(k)
if s[-1] == "1":
  s += "0"
n = len(s)
ls = []
cnt = 0
for i in range(n):
  if s[i] == "0":
    ls.append(cnt)
    cnt = 0
  else:
    cnt += 1
l = len(ls)
sm = sum(ls)
mod = 998244353
dp = [[[0 for i in range(sm+1)] for j in range(sm+1)] for k in range(l+1)]
dp[0][0][0] = 1
smprv = 0
for i in range(1,l+1):
  num = ls[i-1]
  for j in range(smprv+num,sm+1):
    if j == smprv+num:
      dp[i][j][0] = 1
    for k in range(1,j+1):
      for m in range(j+1):
        x = 0
        if num >= m:
          x += dp[i-1][j-m][k]
        else:
          x += dp[i-1][j-m][k-(m-num)]
      dp[i][j][k] = x%mod
  smprv += num
ans = 0
for i in range(sm+1):
  if i <= K:
    ans += dp[-1][-1][i]
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
s,k = input().split()
mod = 998244353
k = int(k)
k = min(150,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 = [[0 for _ in range(k+1)] for _ in range(k+1)]
  for i in range(k+1):
    for j in range(k+1):
      for mag in range(x+1):
        if mag + i > k or mag + j > k:
          continue
        now[i+mag][j+mag] += last[i][j]
        now[i+mag][j+mag] %= mod
      for dim in range(j):
        now[i][dim] += last[i][j]
        now[i][dim] %= mod
  #print(now)
#print(now)
ans = 0
for i in range(k+1):
  ans += now[i][0]
print(ans%mod)

Submission status: Wrong Answer

Solution code:
s,k = input().split()
mod = 998244353
k = int(k)
k = min(100,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 = [[0 for _ in range(k+1)] for _ in range(k+1)]
  for i in range(k+1):
    for j in range(k+1):
      for mag in range(x+1):
        if mag + i > k or mag + j > k:
          continue
        now[i+mag][j+mag] += last[i][j]
        now[i+mag][j+mag] %= mod
      for dim in range(j):
        now[i][dim] += last[i][j]
        now[i][dim] %= mod
  #print(now)
#print(now)
ans = 0
for i in range(k+1):
  ans += now[i][0]
print(ans%mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
MOD = 998244353
S, K = input().split()
D = int(K)*2
N = S.count('0') + 1
M = S.count('1')
f = [0]
for s in S:
    if s == '1':
        f[-1] += 1
    else:
        f.append(0)
F = [f[0]]
for c in f[1:]:
    F.append(F[-1]+c)

cur = defaultdict(int)
cur[(0,0)] = 1 # (m, d)
for i in range(N):
    prev = cur
    cur = defaultdict(int)
    for m in range(M-F[i-1]+1 if i > 0 else M+1):
        d = abs(m - f[i])
        for k, v in prev.items():
            pm, pd = k
            cm = pm + m
            cd = pd + d
            if cm >= F[i] and cm <= M and pd <= D:
                cur[(cm, cd)] += v
                cur[(cm, cd)] %= MOD
ans = sum(cur.values()) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from collections import deque,defaultdict,Counter
def main():
    a = input().split()
    S = a[0]
    K = int(a[1])

    A = []
    cnt = 0
    for i in range(len(S)):
        if S[i] == '0':
            A.append(cnt)
            cnt = 0
        else:
            cnt += 1
    A.append(cnt)

    N = len(A)
    Z = sum(A)

    before = defaultdict(int)
    before[0] = 1
    for i in range(N):
        Z -= A[i]
        now = defaultdict(int)
        for k,v in before.items():
            for j in range(-A[i],K + 1):
                if j + k > Z:
                    break
                if j + k < 0:
                    continue
                now[k + j] += v
                now[k + j] %= MOD
        before = now

    ans = before[0]
    print(ans)  
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
con = 998244353; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	S, K = list(input().split())
	K = int(K)
	num = []
	cnt = 0
	for i in S:
		if i == "0":
			num.append(cnt)
			cnt = 0
		else:
			cnt += 1

	if cnt != 0:
		num.append(cnt)

	num = list(reversed(num))
	# print(num)

	# DP[どこまでみたか][移動回数][1のストック数]
	DP = [[[0] * 610 for i in range(1201)] for j in range(len(num) + 1)]
	DP[0][0][0] = 1
	# print(DP)

	for i in range(len(num)):
		var = num[i]
		for j in range(601):
			for k in range(151):
				for x in range(1, k + 1):
					DP[i + 1][j + x][k - x] += DP[i][j][k]
					DP[i + 1][j + x][k - x] %= con
				for x in range(var + 1):
					DP[i + 1][j + x][k + x] += DP[i][j][k]
					DP[i + 1][j + x][k + x] %= con

	ans = 0
	K2 = min(2 * K, 600)
	for i in range(K2 + 1):
		ans += DP[-1][i][0]

	# print(DP[-1][0][:10])
	# print(DP[-1][1][:10])
	# print(DP[-1][2][:10])

	print(ans % con)



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
S,K=input().split()
K=int(K)
mod=998244353
N=len(S)

num_0=0
num_1=0
for i in range(N):
    if S[i]=="0":
        num_0+=1
    else:
        num_1+=1

facto=[0]*N
facto[0]=1
for i in range(N-1):
    facto[i+1]=facto[i]*(i+2)%mod

ans=facto[N-1]*pow(facto[num_0-1],-1,mod)*pow(facto[num_1-1],-1,mod)
ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
a,n =map(str, input().split())
b=str(a[1:])
ans=0

for i in range(0,int(n)+1):
  for j in range(0,1):
      c=b[i:]+str(a[j])+b[i+1:]
      ans+=1
print(ans*2%998244353)

Submission status: Wrong Answer

Solution code:
s,k = input().split()
K = int(k)
if s[-1] == "1":
  s += "0"
n = len(s)
ls = []
cnt = 0
for i in range(n):
  if s[i] == "0":
    ls.append(cnt)
    cnt = 0
  else:
    cnt += 1
l = len(ls)
sm = sum(ls)
mod = 998244353
dp = [[[0 for i in range(sm+1)] for j in range(sm+1)] for k in range(l+1)]
dp[0][0][0] = 1
smprv = 0
for i in range(1,l+1):
  num = ls[i-1]
  for j in range(smprv+num,sm+1):
    if j == smprv+num:
      dp[i][j][0] = 1
      for k in range(1,sm+1):
        for m in range(j+1):
          if num >= m:
            dp[i][j][k] += dp[i-1][j-m][k]
          else:
            dp[i][j][k] += dp[i-1][j-m][k-(m-num)]
        dp[i][j][k] %= mod
    else:
      for k in range(1,sm+1):
        dp[i][j][k] += dp[i][j-1][k-1]+dp[i-1][j-num][k]
      dp[i][j][k] %= mod
  smprv += num

ans = 0
for i in range(sm+1):
  if i <= K:
    ans += dp[-1][-1][i]
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
[input_l, k] = input().split(' ')
k = int(k)

re_list = [[input_l]]
all_list = [input_l]
for k_idx in range(0, k):
    tmp_re_list = []
    input_l_list = re_list[k_idx]
    for input_l in input_l_list:
        len_input_l = len(input_l)
        for i in range(1, len_input_l):
            for j in range(1, len_input_l):
                add_str = input_l[:j] + input_l[i-1] + input_l[1+j:]
                if add_str not in tmp_re_list:
                    tmp_re_list.append(input_l[:j] + input_l[i-1] + input_l[1+j:])
                if add_str not in all_list:
                    all_list.append(add_str)
    re_list.append(tmp_re_list)
print(len(all_list))

Submission status: Wrong Answer

Solution code:
a,n =map(str, input().split())
b=str(a[2:])
ans=0

for i in range(int(n)+1):
  for j in range(1):
      c=b[i:]+str(a[j])+b[i+1:]
      ans+=1
print(ans*2)

Submission status: Wrong Answer

Solution code:
P = 998244353
S, K = input().split()
N = S.count("0") + 1
A = [len(a) for a in S.split("0")][::-1]
K = int(K)
X = [[0] * N for _ in range(N)]
X[0][0] = 1
for a in A:
    nX = [[0] * N for _ in range(N)]
    Y = [x[:] for x in X]
    for i in range(N-1)[::-1]:
        for j in range(N):
            Y[i][j] += Y[i+1][j]
            if Y[i][j] >= P: Y[i][j] -= P
    Z = [[0] * (N + 1)] + [[0] + x[:] for x in X]
    for i in range(N):
        for j in range(N):
            Z[i+1][j+1] = Z[i][j] + X[i][j]
            if Z[i+1][j+1] >= P: Z[i+1][j+1] -= P
    
    for i in range(N):
        for j in range(N):
            nX[i][j] += Y[i][j]
            t = min(a, i, j)
            nX[i][j] += Z[i][j] - Z[i-t][j-t]
            nX[i][j] %= P
    X = nX
print(sum(X[0][:K+1]) % P)

Submission status: Wrong Answer

Solution code:
s,k=map(int,input().split())

Submission status: Time Limit Exceeded

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]*(K+1) for _ in range(l+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
    for i in range(1,len(sep)):
        ori=sep[-1-i]
        for j in range(l+1):
            dpi=dp[i][j]
            dpp=dp[i-1]
            for k in range(K+1):
                for pj in range(max(0,j-ori),j):
                    pk=k-(j-pj)
                    if pk>=0:
                        dpi[k]+=dpp[pj][pk]
                        dpi[k]%=mod
                for pj in range(j,l+1):
                    dpi[k]+=dpp[pj][k]
                    dpi[k]%=mod

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




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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]*(K+1) for _ in range(l+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
    for i in range(1,len(sep)):
        ori=sep[-1-i]
        for j in range(l+1):
            for k in range(K+1):
                for pj in range(max(0,j-ori),j):
                    pk=k-(j-pj)
                    if pk>=0:
                        dp[i][j][k]+=dp[i-1][pj][pk]
                        dp[i][j][k]%=mod
                for pj in range(j,l+1):
                    dp[i][j][k]+=dp[i-1][pj][k]
                    dp[i][j][k]%=mod

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




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
s,k=input().split();k,o,c,z,L,O=int(k),s.count("1")+1,0,0,[],998244353;M,r=min(o,k+1),range
for i in s:
 if i=="0":L+=[c];c=0
 else:c+=1
d=[[0]*M for _ in r(o)];d[0][0]=1
for i in L:
 D=[[0]*M for _ in r(o)]
 for j in r(o):
  for l in r(max(z+i-j,0),o-j):
   m=max(l-i,0)
   for p in r(min(j+1,M-m)):D[j+l][p+m]=(D[j+l][p+m]+d[j][p])%O
 z+=i;d=D
print(sum([sum(i)for i in d])%O)