Problem:


Score : 600 points

Problem Statement

Given are a sequence of N positive integers A_1, A_2, \ldots, A_N and another positive integer S.

For a non-empty subset T of the set \{1, 2, \ldots , N \}, let us define f(T) as follows:

f(T) is the number of different non-empty subsets \{x_1, x_2, \ldots , x_k \} of T such that A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.

Find the sum of f(T) over all 2^N-1 subsets T of \{1, 2, \ldots , N \}. Since the sum can be enormous, print it modulo 998244353.

Constraints

All values in input are integers.

1 \leq N \leq 3000

1 \leq S \leq 3000

1 \leq A_i \leq 3000

Input

Input is given from Standard Input in the following format:

N S
A_1 A_2 ... A_N

Output

Print the sum of f(T) modulo 998244353.

Sample Input 1

3 4
2 2 4

Sample Output 1

6

For each T, the value of f(T) is shown below. The sum of these values is 6.

f(\{1\}) = 0

f(\{2\}) = 0

f(\{3\}) = 1 (One subset \{3\} satisfies the condition.)

f(\{1, 2\}) = 1 (\{1, 2\})

f(\{2, 3\}) = 1 (\{3\})

f(\{1, 3\}) = 1 (\{3\})

f(\{1, 2, 3\}) = 2 (\{1, 2\}, \{3\})

Sample Input 2

5 8
9 9 9 9 9

Sample Output 2

0

Sample Input 3

10 10
3 1 4 1 5 9 2 6 5 3

Sample Output 3

3296



Sample input:
3 4
2 2 4


Sample output:
6

Submission status: Runtime Error

Solution code:
# coding: utf-8
#import numpy as np
import re
import math
from collections import defaultdict
from collections import deque
import collections
from fractions import Fraction
import bisect
from queue import PriorityQueue
import itertools
from copy import deepcopy
import random
import time
import os
import sys
import datetime
from functools import lru_cache
from functools import reduce
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
alphabet="abcdefghijklmnopqrstuvwxyz"
numbers="0123456789"
mod=int(10**9+7)
inf=int(10**19)
class Edge():
    def __init__(self,x,y,val=1):
        self.x=x
        self.y=y
        self.val=val
class unionfind():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):
            self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def yn(b):
    if b:print("yes")
    else:print("no")
def Yn(b):
    if b:print("Yes")
    else:print("No")
def YN(b):
    if b:print("YES")
    else:print("NO")
def ispow(a,b):
    now=b
    while now<a:
        now*=b
    return now==a
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n):
    if n==0:return []
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    ret=[]
    for a in range(n+1):
        if(A[a]):ret.append(a)
    return ret
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(bbool,ret1,ret2):
    if bbool:return ret1
    else:return  ret2
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n):
    b = 2
    ret=defaultdict(int)
    while b * b <= n:
        while n % b == 0:
            n //= b
            ret[b]+=1
        b+=1
    if n > 1:ret[n]+=1
    return ret
def pm(x):
    return x//abs(x)
def inputintlist(): 
    return list(map(int,input().split()))
def inputfloatlist(): 
    return list(map(float,input().split()))
def tozero(A):
    ret=[None]*len(A)
    for a in range(len(A)):
        ret[a]=A[a]-1
    return ret
def istanchouzouka(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>=a:
            f=False
        prev=a
    return f
def istanchouhigensyou(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>a:
            f=False
        prev=a
    return f
def getallsum(A):
    s=sum(A)
    dp=defaultdict(int)
    dp[0]=1
    for a in range(0,len(A)):
        for b in range(s,-1,-1):
            if b-A[a]>=0:
                dp[b]+=dp[b-A[a]]
    return dp
def yuukoutomukou(edges):
    ret=deepcopy(edges)
    for edge in edges:
        if not edge.x==edge.y:
            ret.append(Edge(edge.y,edge.x,edge.val))
    return ret
def dijkstra(edges,V,start):
    mincost=[inf]*V
    G=[[] for a in range(V)]
    for edge in edges:
        G[edge.x].append([edge.val,edge.y])
    Q=PriorityQueue()
    Q.put([0,start])#[cost,x]
    while not Q.empty():
        nowcost,nowx=Q.get()
        if mincost[nowx]==inf:
            mincost[nowx]=nowcost
            for cost,y in G[nowx]:
                newcost=nowcost+cost
                Q.put([newcost,y])
    return mincost
def warshallfloyd(edges,V):
    mincost=[[inf for b in range(V)] for a in range(V)]
    for a in range(V):mincost[a][a]=0
    for edge in edges:
        mincost[edge.x][edge.y]=min(mincost[edge.x][edge.y],edge.val)#x→yが複数ある場合のためにmin()する
    for k in range(V):
        for s in range(V):
            for t in range(V):
                if mincost[s][k]==inf or mincost[k][t]==inf:continue
                mincost[s][t]=min(mincost[s][t],mincost[s][k]+mincost[k][t])
    return mincost
def bellemanford(edges,V,start):
    mincost=[inf]*V
    mincost[start]=0
    for _ in range(V):
        for edge in edges:
            if mincost[edge.x]==inf:continue
            mincost[edge.y]=min(mincost[edge.y],mincost[edge.x]+edge.val)
    return mincost
def ruisekiwa(A):
    ret=[0]*(len(A)+1)
    for a in range(len(A)):
        ret[a+1]=ret[a]+A[a]
    return ret
def getmd(x1,y1,x2,y2):
    return abs(x1-x2)+abs(y1-y2)
def geted(x1,y1,x2,y2):
    return math.sqrt((x1-x2)**2+(y1-y2)**2)
class fordfulkerson():
    def __init__(self,edges,V,s,t):
        self.V=V
        self.used=[False]*V
        self.G=[[] for a in range(V)]
        self.s=s
        self.t=t
        for edge in edges:
            self.G[edge.x].append({"x":edge.x,"y":edge.y,"cap":edge.val,"rev":len(self.G[edge.y])})
            self.G[edge.y].append({"x":edge.y,"y":edge.x,"cap":0,"rev":len(self.G[edge.x])-1})
    def dfs(self,v,t,f=inf):
        if v==t:return f
        self.used[v]=True
        for a in range(len(self.G[v])):
            x=self.G[v][a]["x"]
            y=self.G[v][a]["y"]
            cap=self.G[v][a]["cap"]
            rev=self.G[y][self.G[x][a]["rev"]]
            if self.used[y] or cap==0:continue
            f2=self.dfs(y,t,min(f,cap))
            if f2>0:
                self.G[v][a]["cap"]-=f2
                rev["cap"]+=f2
                return f2
        return 0
    def maxflow(self):
        flow=0
        while True:
            self.used=[False]*V
            zouka=self.dfs(self.s,self.t)
            if zouka==0:break
            flow+=zouka
        return flow



######################################################################################################
def f(A):
    ssum=sum(A)
    dp=[[0 for b in range(ssum+1)] for a in range(len(A)+1)]
    dp[0][0]=1
    for i in range(1,len(A)+1):
        for s in range(ssum+1):
            dp[i][s]=dp[i-1][s]*2
            if s-A[i-1]>=0:
                dp[i][s]+=dp[i-1][s-A[i-1]]
            dp[i][s]%=998244353
    return dp
n,s=inputintlist()
A=inputintlist()
mmod=998244353
dp=f(A)
ans=dp[-1][s]
print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
#import numpy as np
import re
import math
from collections import defaultdict
from collections import deque
import collections
from fractions import Fraction
import bisect
from queue import PriorityQueue
import itertools
from copy import deepcopy
import random
import time
import os
import sys
import datetime
from functools import lru_cache
from functools import reduce
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
alphabet="abcdefghijklmnopqrstuvwxyz"
numbers="0123456789"
mod=int(10**9+7)
inf=int(10**19)
class Edge():
    def __init__(self,x,y,val=1):
        self.x=x
        self.y=y
        self.val=val
class unionfind():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):
            self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def yn(b):
    if b:print("yes")
    else:print("no")
def Yn(b):
    if b:print("Yes")
    else:print("No")
def YN(b):
    if b:print("YES")
    else:print("NO")
def ispow(a,b):
    now=b
    while now<a:
        now*=b
    return now==a
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n):
    if n==0:return []
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    ret=[]
    for a in range(n+1):
        if(A[a]):ret.append(a)
    return ret
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(bbool,ret1,ret2):
    if bbool:return ret1
    else:return  ret2
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n):
    b = 2
    ret=defaultdict(int)
    while b * b <= n:
        while n % b == 0:
            n //= b
            ret[b]+=1
        b+=1
    if n > 1:ret[n]+=1
    return ret
def pm(x):
    return x//abs(x)
def inputintlist(): 
    return list(map(int,input().split()))
def inputfloatlist(): 
    return list(map(float,input().split()))
def tozero(A):
    ret=[None]*len(A)
    for a in range(len(A)):
        ret[a]=A[a]-1
    return ret
def istanchouzouka(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>=a:
            f=False
        prev=a
    return f
def istanchouhigensyou(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>a:
            f=False
        prev=a
    return f
def getallsum(A):
    s=sum(A)
    dp=defaultdict(int)
    dp[0]=1
    for a in range(0,len(A)):
        for b in range(s,-1,-1):
            if b-A[a]>=0:
                dp[b]+=dp[b-A[a]]
    return dp
def yuukoutomukou(edges):
    ret=deepcopy(edges)
    for edge in edges:
        if not edge.x==edge.y:
            ret.append(Edge(edge.y,edge.x,edge.val))
    return ret
def dijkstra(edges,V,start):
    mincost=[inf]*V
    G=[[] for a in range(V)]
    for edge in edges:
        G[edge.x].append([edge.val,edge.y])
    Q=PriorityQueue()
    Q.put([0,start])#[cost,x]
    while not Q.empty():
        nowcost,nowx=Q.get()
        if mincost[nowx]==inf:
            mincost[nowx]=nowcost
            for cost,y in G[nowx]:
                newcost=nowcost+cost
                Q.put([newcost,y])
    return mincost
def warshallfloyd(edges,V):
    mincost=[[inf for b in range(V)] for a in range(V)]
    for a in range(V):mincost[a][a]=0
    for edge in edges:
        mincost[edge.x][edge.y]=min(mincost[edge.x][edge.y],edge.val)#x→yが複数ある場合のためにmin()する
    for k in range(V):
        for s in range(V):
            for t in range(V):
                if mincost[s][k]==inf or mincost[k][t]==inf:continue
                mincost[s][t]=min(mincost[s][t],mincost[s][k]+mincost[k][t])
    return mincost
def bellemanford(edges,V,start):
    mincost=[inf]*V
    mincost[start]=0
    for _ in range(V):
        for edge in edges:
            if mincost[edge.x]==inf:continue
            mincost[edge.y]=min(mincost[edge.y],mincost[edge.x]+edge.val)
    return mincost
def ruisekiwa(A):
    ret=[0]*(len(A)+1)
    for a in range(len(A)):
        ret[a+1]=ret[a]+A[a]
    return ret
def getmd(x1,y1,x2,y2):
    return abs(x1-x2)+abs(y1-y2)
def geted(x1,y1,x2,y2):
    return math.sqrt((x1-x2)**2+(y1-y2)**2)
class fordfulkerson():
    def __init__(self,edges,V,s,t):
        self.V=V
        self.used=[False]*V
        self.G=[[] for a in range(V)]
        self.s=s
        self.t=t
        for edge in edges:
            self.G[edge.x].append({"x":edge.x,"y":edge.y,"cap":edge.val,"rev":len(self.G[edge.y])})
            self.G[edge.y].append({"x":edge.y,"y":edge.x,"cap":0,"rev":len(self.G[edge.x])-1})
    def dfs(self,v,t,f=inf):
        if v==t:return f
        self.used[v]=True
        for a in range(len(self.G[v])):
            x=self.G[v][a]["x"]
            y=self.G[v][a]["y"]
            cap=self.G[v][a]["cap"]
            rev=self.G[y][self.G[x][a]["rev"]]
            if self.used[y] or cap==0:continue
            f2=self.dfs(y,t,min(f,cap))
            if f2>0:
                self.G[v][a]["cap"]-=f2
                rev["cap"]+=f2
                return f2
        return 0
    def maxflow(self):
        flow=0
        while True:
            self.used=[False]*V
            zouka=self.dfs(self.s,self.t)
            if zouka==0:break
            flow+=zouka
        return flow



######################################################################################################
def f(A):
    ssum=sum(A)
    dp=[[0 for b in range(ssum+1)] for a in range(len(A)+1)]
    dp[0][0]=1
    for i in range(1,len(A)+1):
        for s in range(ssum+1):
            dp[i][s]=dp[i-1][s]*2
            if s-A[i-1]>=0:
                dp[i][s]+=dp[i-1][s-A[i-1]]
    return dp
n,s=inputintlist()
A=inputintlist()
mmod=998244353
dp=f(A)
ans=dp[-1][s]
print(ans)

Submission status: Runtime Error

Solution code:
# Import
from collections import deque
import math

# I/O
def read(): return input()
def read_int(): return int(input())
def read_array(type=int): return [type(i) for i in input().split()]
def read_tupple(type=None):
    tmp = input().split()
    if type is None: return map(int, tmp)
    assert len(tmp) == len(type)
    return [type[i](tmp[i]) for i in range(len(tmp))]

MOD = 998244353
N, S = read_tupple()
A = read_array()

dp = [[0 for j in range(S+1)] for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for j in range(S+1):
        dp[i + 1][j] += 2 * dp[i][j]
        if j - A[i] >= 0:
            dp[i + 1][j] += dp[i][j - A[i]]
        
        while dp[i+1][j] > MOD:
			dp[i+1][j] -= MOD
        
print(dp[N][S])

Submission status: Runtime Error

Solution code:
n, s = map(int, input().split())
la = [int(i) for i in input().split()]


dks = [[None] * (s + 1) for _ in range(n)]


def getks(i=0, s=s):
    if s < 0:
        return 0
    elif i == n:
        return int(s == 0)
    elif dks[i][s] is not None:
        return dks[i][s]
    else:
        ks = 2 * getks(i + 1, s) + getks(i + 1, s - la[i])
        dks[i][s] = ks
        return ks


answer = getks()
print(answer)

Submission status: Runtime Error

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, S = iim()
    A = list(iim())
    mod = 998244353
    S1 = S + 1

    dp = [0] * (S+1)
    dp1 = dp[:]
    dp[0] = 1
    for ai in A:
        sa = S - ai
        for i in range(sa):
            dp1[i] = 2 * dp[i]
        for i in range(sa, S1):
            dp1[i] = 2 * dp[i] + dp[i-ai]
        dp, dp1 = dp1, dp

    print(dp[-1])


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())
from collections import defaultdict

def resolve():
    N, S = iim()
    A = list(iim())
    mod = 998244353

    dp = [0] * (S+1)
    dp1 = dp[:]
    dp[0] = 1
    for ai in A:
        for i in range(ai):
            dp1[i] = 2 * dp[i]
        for i in range(ai, S+1):
            dp1[i] = 2 * dp[i] + dp[i-ai]
        dp, dp1 = dp1, dp

    print(dp[-1])


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
MOD=998244353
n,s=map(int,input().split())
a=list(map(int,input().split()))
al=sum(a)
dp=[[0]*(al+1) for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    for j in range(al+1):
        if j==0:
            dp[i+1][j]=pow(2,i+1,MOD)
            continue
        dp[i+1][j]=(dp[i+1][j]+(dp[i][j]*2%MOD))%MOD
        if j-a[i]>=0:
            dp[i+1][j]=(dp[i+1][j]+dp[i][j-a[i]])%MOD
print(dp[n][s])

Submission status: Runtime Error

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

def calc():
  mod=998244353
  n,s=map(int,input().split())
  arr=list(map(int,input().split()))
  dp=[0]*(s+1)
  dp[0]=1
  ans=0
  for i in range(1,n+1):
    val=arr[i-1]
    for k in range(s,-1,-1):
      dp[k]*=2
      dp[k]%=mod
      if k>=val and dp[k-val]!=0:
        dp[k]+=dp[k-val]
        dp[k]%=mod
  print(dp[n]%mod)
calc()

Submission status: Runtime Error

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

def calc():
  mod=998244353
  n,s=map(int,input().split())
  arr=list(map(int,input().split()))
  dp=[0]*(s+1)
  dp[0]=1
  ans=0
  for i in range(1,n+1):
    val=arr[i-1]
    for k in range(s,-1,-1):
      dp[k]*=2
      if k>=val and dp[k-val]!=0:
        dp[k]+=dp[k-val]
  print(dp[n])
calc()

Submission status: Runtime Error

Solution code:
import numpy as np
def main():
    n,s=map(int,input().split())
    A=list(map(int,input().split()))
    maxA=max(A)
    dp=np.array([0 for i in range(s+1)])
    dp[0]=1
    for ai in A:
        tmp=dp[:-ai].copy()
        #print(tmp)
        dp*=2
        dp[ai:]+=tmp
    print(dp[s])
    

if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353

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

dp[0][0]=2
dp[0][A[0]]=1
for i in range(N-1):
    for j in range(S+1):
        dp[i+1][j]+=dp[i][j]*2
        dp[i+1][j]%=mod
        if j+A[i+1]<=S:
            dp[i+1][j+A[i+1]]+=dp[i][j]
            dp[i+1][j+A[i+1]]%=mod

print(dp[N-1][S]%mod)

Submission status: Runtime Error

Solution code:
class Inv:
  def __init__(s, mod):
    s.MOD = mod
  def modpow(s, a, n):
    res = 1
    while n > 0:
      if n & 1:
        res = res * a % s.MOD
      a = a * a % s.MOD
      n >>= 1
    return res
  def invx(s, a):
    return s.modpow(a, s.MOD - 2)
  def invpowL(s, a, n): # a^-x (0 <= x <= n)リスト
    ia = s.invx(a)
    L = [1] * (n + 1)
    for i in range(1, n + 1):
      L[i] = L[i - 1] * ia % s.MOD
    return L
  def invL(s, n): # 0 <= x <= n 逆元リスト
    I = [0, 1]
    for i in range(2, n + 1):
      I.append(s.MOD - I[s.MOD % i] * (s.MOD // i) % s.MOD)
    return I


N, S = list(map(int, input().split()))
A = list(map(int, input().split()))
MOD = 998244353

DP = [[0] * (S + 1) for _ in range(N + 1)]

inv = Inv(MOD)
v = inv.invx(2)

p = inv.modpow(2, N - 1)
for i in range(1, N + 1):
  a = A[i - 1]
  if a > S: 
    for j in range(S + 1):
      DP[i][j] = DP[i - 1][j]
  for j in range(a):
    DP[i][j] = DP[i - 1][j]
  DP[i][a] = (DP[i - 1][a] + p) % MOD
  for j in range(a + 1, S + 1):
    DP[i][j] = (DP[i - 1][j] + DP[i - 1][j - a] * v) % MOD

print(DP[-1][S])

Submission status: Runtime Error

Solution code:
class Inv:
  def __init__(s, mod):
    s.MOD = mod
  def modpow(s, a, n):
    res = 1
    while n > 0:
      if n & 1:
        res = res * a % s.MOD
      a = a * a % s.MOD
      n >>= 1
    return res
  def invx(s, a):
    return s.modpow(a, s.MOD - 2)
  def invpowL(s, a, n): # a^-x (0 <= x <= n)リスト
    ia = s.invx(a)
    L = [1] * (n + 1)
    for i in range(1, n + 1):
      L[i] = L[i - 1] * ia % s.MOD
    return L
  def invL(s, n): # 0 <= x <= n 逆元リスト
    I = [0, 1]
    for i in range(2, n + 1):
      I.append(s.MOD - I[s.MOD % i] * (s.MOD // i) % s.MOD)
    return I


N, S = list(map(int, input().split()))
A = list(map(int, input().split()))
MOD = 998244353

DP = [[0] * (S + 1) for _ in range(N + 1)]

inv = Inv(MOD)
v = inv.invx(2)

p = inv.modpow(2, N - 1)
for i in range(1, N + 1):
  a = A[i - 1]
  if a > S: 
    for j in range(S + 1):
      DP[i][j] = DP[i - 1][j]
  for j in range(a):
    DP[i][j] = DP[i - 1][j]
  DP[i][a] = (DP[i - 1][a] + p) % MOD
  for j in range(a + 1, S + 1):
    DP[i][j] = (DP[i - 1][j] + DP[i - 1][j - a] * v) % MOD

for i in DP:
  print(i)
print(DP[-1][S])

Submission status: Runtime Error

Solution code:
def saiki(i,k,sum): # aのi番目について、kコ目のa要素、これまでの和
    if i>=n:
        return
    if sum+a[i]==s:
        times[k]+=1
    elif sum+a[i]<s:
        saiki(i+1,k+1,sum+a[i])
    saiki(i+1,k,sum)

import numpy as np
n,s=map(int,input().split())
a=list(map(int,input().split()))
a.sort(key=lambda x:-x)
# print(a)
times=[0 for _ in range(n)]
saiki(0,1,0)
# print(times)
ans=0
for i in range(n):
    ans+=times[i]*2**(n-i)
    ans%=998244353
print(ans)

Submission status: Runtime Error

Solution code:
def saiki(i,k,sum): # aのi番目について、kコ目のa要素、これまでの和
    if i>=n:
        return
    if sum+a[i]==s:
        times[k]+=1
    elif sum+a[i]<s:
        saiki(i+1,k+1,sum+a[i])
    saiki(i+1,k,sum)

import numpy as np
n,s=map(int,input().split())
a=list(map(int,input().split()))
a.sort(key=lambda x:-x)
# print(a)
times=[0 for _ in range(n)]
saiki(0,1,0)
# print(times)
ans=0
for i in range(n):
    ans+=times[i]*2**(n-i)
print(ans)

Submission status: Runtime Error

Solution code:
import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,s = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    mod = 998244353
    two = [1]*(n+1)
    for i in range(n):
        two[i+1] = two[i]*2%mod
    dp = np.zeros((n+1,s+1),dtype = int)
    for i,ai in enumerate(a):
        if ai > s:
            continue
        for si in range(s):
            dp[s-si][ai:] += dp[s-si-1][:-ai]
        dp[1][ai] += 1
    ans = 0
    for i in range(n+1):
        dpi = dp[i]
        ans = (ans+(dpi[s]*two[n-i])%mod)%mod
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import numpy as np

N,S, *A = map(int, sys.stdin.buffer.read().split())
mod = 998244353
A = sorted(A)

answer = np.zeros(S+1).astype(np.int64) # [0 for _ in range(S+1)]
power2 = 1

total = 0
for a in A:
  total = min(S,a+total)
  answer[a+1:total+1] = (2*answer[a+1:total+1]+answer[1:total-a+1])%mod
  answer[a] = (2*answer[a]+power2)%mod
  answer[1:a] = (2*answer[1:a])%mod
  power2 = (2*power2)%mod

print(answer[S])

Submission status: Runtime Error

Solution code:
import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,s = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    mod = 998244353
    two = [1]*(n+1)
    for i in range(n):
        two[i+1] = two[i]*2%mod
    dp = np.zeros((n+1,s+1),dtype = int)
    for i,ai in enumerate(a):
        if ai > s:
            continue
        dp1 = np.zeros((n+1,ai),dtype=int)
        dp2 = np.zeros((1,s+1-ai),dtype=int)
        dp3 = np.array([l[:s+1-ai] for l in dp[:-1]])
        dp4 = np.block([[dp2],[dp3]])
        dp5 = np.block([dp1,dp4])
        dp += dp5
        dp[1][ai] += 1
    ans = 0
    for i in range(n+1):
        dp[i] = dpi
        ans = (ans+(dpi[s]*two[n-i])%mod)%mod
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n,s=map(int,input().split())
    N=[i+1 for i in range(n)]
    list1=[]
    pattern=[]
    A=list(map(int,input().split()))

    ft=0  
    dict={}
    for i in range(n+1):
        dict[i]=[]
    for i in range(1,2**n):
        list2=[]
        for j in range(n):
            if (i >> j) &1 == 1:
                list2.append(N[j])
        pattern=[]
        for x in range(1,2**len(list2)):
            pt=[]
            for y in range(len(list2)):
                if (x>>y)&1==1:
                    pt.append(list2[y])
            pattern.append(pt)
    # print(pattern)

        for p in pattern:
            sum=0
            if p in dict[len(p)]:
                ft+=1
            else:
                for x in p:
                    sum+=A[x-1]
                if sum==s:
                    dict[len(p)].append(p)
                    ft+=1
                    ft=ft%998244353
    print(ft%998244353)

if __name__"__main__":
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
lister = []
for i in range(n):
    lister.append([int(i) for i in input().split()])
 
if n % 2 == 1:
    lister.sort(key=lambda x:x[0])
    miner = lister[n//2][0]
    lister.sort(key=lambda x:x[1])
    maxer = lister[n//2][1]
    print(maxer- miner + 1)
else:
    lister.sort(key=lambda x:x[0])
    miner = lister[n//2 - 1][0]
    miner += lister[n//2][0]
    lister.sort(key=lambda x:x[1])
    maxer = lister[n//2][1]
    maxer += lister[n//2 - 1][1]
    print(1 + (maxer- miner))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    N,S=pin()
    A=list(pin())

    #print(A)

    #dp[i]"s""n" i番めまで見る。n個使った。和がsになった2重の辞書…
    dp=[dict()for i  in range(N+1)]
    #sを辞書として管理するとうまく配るDPが実装できるよね
    dp[0].setdefault(0,dict())
    dp[0][0].setdefault(0,1)
    

    for i in range(N):#
        kouho=A[i]
        for s in dp[i]:
            ref=dp[i][s]
            for k,v in ref.items():
                ##print(k,v)
                #saiyousinai
                dp[i+1].setdefault(s,dict())
                dp[i+1][s].setdefault(k,0)
                dp[i+1][s][k]+=v
                #saiyou        
                x=s+kouho
                ##print(x)
                if x<=S:
                    dp[i+1].setdefault(x,dict())
                    dp[i+1][x].setdefault(k+1,0)
                    dp[i+1][x][k+1]+=v
                
    temp=(dp[-1][S])
    ans=0
    for p,q in temp.items():
        if N-p>=0:
            ans+=q*(2**(N-p))
    print(ans)
#%%submit!
resolve()

Submission status: Runtime Error

Solution code:
from collections import Counter
N, S = map(int, input().split())
As = list(map(int, input().split()))

cts = [Counter() for _ in range(min(S, N)+1)]
cts[0][0] = 1
for a in As:
    for i in range(S-1, -1, -1):
        ct = cts[i]
        for v, n in ct.items():
            if v+a <= S:
                cts[i+1][v+a] += n

ans = 0
MOD = 998244353
for i in range(1, min(S, N)+1):
    ct = cts[i]
    ans += ct[S] * pow(2, (N-i), MOD)
    ans %= MOD
print(ans % MOD)

Submission status: Runtime Error

Solution code:
from collections import Counter
N, S = map(int, input().split())
As = list(map(int, input().split()))

cts = [Counter() for _ in range(S+1)]
cts[0][0] = 1
for a in As:
    for i in range(S-1, -1, -1):
        ct = cts[i]
        for v, n in list(ct.items()):
            if v+a <= S:
                cts[i+1][v+a] += n

ans = 0
MOD = 998244353
for i in range(1, S+1):
    ct = cts[i]
    ans += ct[S] * pow(2, (N-i), MOD)
    ans %= MOD
print(ans % MOD)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
import itertools



n, s = map(int, input().split())

cnt=0
Li = [int(a) for a in input().split()]
Li = np.array(Li)

for i in range(1, n+1):
    T_gun = np.array(list(itertools.combinations(Li, i)))
    seki = t_gun.sum(axis=1)
    cnt += sum(seki == s) * 2**(n-i)
    if cnt >= 998244353:
        cnt = cnt % 998244353

print(cnt)

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
fac=[1,1]
for i in range(2,3010):
    fac.append(fac[-1]*i%mod)
ifac=[pow(i,mod-2,mod) for i in fac]

def comb(a,b):
    return(fac[a]*ifac[a-b]*ifac[b]%mod)


dp=[[] for n in range(3000)]
for n in range(N):
    a=A[n]
    for s in range(0,3000)[::-1]:
        if s+a<=3000:
            for h in dp[s]:
                dp[s+a].append(h+1)
    dp[a].append(1)
c=0
#print(dp[S])
for a in dp[S]:
    c+=comb(N,a)
    c%=mod
print(c)

Submission status: Runtime Error

Solution code:
ans=0
n,s=map(int,input().split())
ar=list(map(int,input().split()))
mod=998244353

def func(b,sel,pos):
    global ans
    if b==s:
        ans+=pow(2,(n-sel),mod)
    #print(b,sel,pos,ans)
    if pos<n-1:
        func(b+ar[pos+1],sel+1,pos+1)
        if b<s:
            func(b,sel,pos+1)
    

func(ar[0],1,0)
func(0,0,0)
print(ans%mod)