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:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 998244353
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n2 = [1 for _ in range(3010)]
for i in range(1, 3010):
    n2[i] = n2[i - 1] * 2 % mod

n, s = MAP()
a = LIST()
dp = [[0 for _ in range(s + 1)] for _ in range(n)]
if s >= a[0]:
    dp[0][a[0]] = 1
#print(a[0], dp[0])
for i in range(1, n):
    for j in range(1, a[i]):
        dp[i][j] = dp[i - 1][j] * 2
        dp[i][j] %= mod
    if a[i] <= s:
        dp[i][a[i]] = dp[i - 1][a[i]] * 2 + n2[i]
        dp[i][a[i]] %= mod
    for j in range(a[i] + 1, s + 1):
        dp[i][j] = dp[i - 1][j] * 2
        if dp[i - 1][j - a[i]]:
            dp[i][j] += dp[i - 1][j - a[i]]# * 2 + dp[i - 1][j - a[i]]
        dp[i][j] %= mod
    #print(a[i], dp[i])
print(dp[n - 1][s])

Submission status: Runtime Error

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

def func(b,sel,pos):
    global ans
    if b==s:
        ans+=1<<(n-sel)
    #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)

Submission status: Runtime Error

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

def BFS(now,i,pattern):
    if now == S:
        P.append(pattern)
    else:
        if i < N:
            if now + A[i] <= S:
                BFS(now+A[i],i+1,pattern+1)

            BFS(now,i+1,pattern)

BFS(0,0,0)

ans = 0
n = len(P)
for i in range(n):
    l = P[i]
    ans += 2**(N-l)
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
mod = 998244353
N, S = map(int,input().split())
A = list(map(int,input().split()))
dp = [[0 for i in range(S+1)] for j in range(N+1)]
dp[0][0] = 1

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

print(dp[N][S])
z

Submission status: Runtime Error

Solution code:
from collections import deque

def rec(dp, a, i, j, keiro, ans):
    if i == 0:
        if j == 0:
            ans.append(set(keiro))
        return
    
    if dp[i - 1][j] != 0:
        rec(dp, a, i - 1, j, keiro, ans)
    
    if j - a[i-1] >= 0 and dp[i - 1][j - a[i - 1]]:
        keiro.appendleft(i)
        rec(dp, a, i - 1, j - a[i-1], keiro, ans)
        keiro.popleft()

def main():
    n,s = map(int, input().split())
    a = list(map(int, input().split()))
    
    dp = [[0 for i in range(3010)] for j in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(3010):
            dp[i + 1][j] += dp[i][j]
            if (j + a[i] < 3010):
                dp[i + 1][j + a[i]] += dp[i][j]
    
    keiro = deque()
    ans = []
    
    rec(dp, a, n, s, keiro, ans)
    
    answer = 0
    
    for i in range(len(ans)):
        m = len(ans[i])
        add = 1
        for j in range(n - m):
            add *= 2
            add %= mod
        answer += add
        answer %= mod
    
    print(answer)

if __name__ == "__main__":
    mod = 998244353
    main()

Submission status: Runtime Error

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

def BFS(now,i,pattern):
    if now == S:
        P.append(pattern)
    else:
        if i < N:
            if now + A[i] <= S:
                BFS(now+A[i],i+1,pattern+"1")

            BFS(now,i+1,pattern+"0")

BFS(0,0,"")

ans = 0
n = len(P)
for i in range(n):
    l = 0
    for p in P[i]:
        if p == "1":
            l += 1
    ans += 2**(N-l)
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
ans=1
for i in range(N):
    ans=ans*A[]
    if ans>10**18:
        ans=-1
        break
    elif ans==0:
        break
print(ans)

Submission status: Runtime Error

Solution code:
n, s = map(int, input().split())
a = [int(i) for i in input().split()]
mod = 998244353
dp = [0 for _ in range(3000 + max(a) + 1)]
for j in a:
    for i in range(s):
        if i == 0:
            dp[i + j] = dp[i] + 1
        else:
            if d[i] > 0:
                dp[i + j] = dp[i] + 1
print(dp[s] % mod)

Submission status: Runtime Error

Solution code:
n,s=map(int,input().split())
mod=998244353
A=list(map(int,input().split()))
dp=[[]*(s+1) for i in range(n+1)]
dp[0][0]=[1]
for i in range(n+1):
  dp[i][0]=[1]
for i in range(1,n+1):
  for j in range(1,s+1):
    dp[i][j].append(dp[i-1][j])
    if j+A[i]<=s:
      dp[i][j+A[i]].append(dp[i][j]+1)
ans=0
for i in range(len(dp[n][s])):
  ans=ans+dp[n][s][i]*pow(2,n-dp[n][s][i],mod)
print(ans%mod)

Submission status: Runtime Error

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

MOD = 998244353
dp = [[[0, []] for i 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 - A[i]):
        if dp[i][j][0]:
            dp[i + 1][j] = dp[i][j]
            dp[i + 1][j + A[i]][0] += dp[i][j][0]
            dp[i + 1][j + A[i]][1] += list(map(lambda x: x + 1, dp[i][j][1]))


ans = 0
for i in range(N + 1):
    ans += sum(dp[i][S][0])
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import combinations

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

subsets=[]
ans = 0
for i in range(min(s,len(items) + 1):
    for c in combinations(items, i):
        if sum(c) == s:
            ans += 2**(n-len(c))
print(ans)

Submission status: Runtime Error

Solution code:
#from collections import deque,defaultdict
from sys import stdin
input = stdin.readline
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n,s = inm()
a = inl()
dp = [[0]*(s+1) for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = 1
sm = 0
for i in range(1,n+1):
    for j in range(s):
        if dp[i-1][j]>0 and j+a[i-1]<=s:
            dp[i][j+a[i-1]] += dp[i-1][j]
            if j+a[i-1]==s:
                sm = (sm+dp[i-1][j]*pow(2,n-i+1,R))%R
    ddprint(dp)
print(sm)

Submission status: Runtime Error

Solution code:
import sys
import itertools

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read
MOD = 998244353

def main():
    N, S = map(int, readline().split())
    A = list(map(int, input().split()))
    B = A.copy()
    B.sort(reverse=True)
    tmp = 0
    for i in range(N):
        tmp += B.pop()
        if tmp > S:
            m = i
            break
    pair = []
    for j in range(1, m):
        for p in itertools.combinations(range(0, N), j):
            base = 0
            for q in p:
                base += A[q]
                if base > S:
                    break
            if base == S:
                pair.append(m)

    ans = 0
    for p in pair:
        ans += pow(2, N - p)
        ans %= MOD

    print(ans%MOD)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,s=map(int,input().split())
a=list(map(int,input().split()))
l=list()
for i in range(n):
    if a[i]>n:
        l.append(i)
for i in l.reverse():
    a.remove(i)
b=list()
for i in range(n):
    b.append(0)
now=0
weight=0
ans=0
while True:
    if now>=n:
        if not 1 in b:
            break
        else:
            idx="".join(map(str,b)).rfind("1")
            b[idx]=0
            now=idx+1
            weight-=a[idx]
            continue
    if weight+a[now]<s:
        b[now]=1
        weight+=a[now]
        now+=1
        continue
    elif weight+a[now]==s:
        x=n-sum(b)-1
        y=1
        for i in range(x):
            y*=2
            y=y%998244353
        ans+=y
        now+=1
    else:
        now+=1
        
print(ans%998244353)

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) for _ in range(n+1)] for _ in range(n+1)]
  dp[0][0][0]=1
  for i in range(1,n+1):
    val=arr[i-1]
    for j in range(i,-1,-1):
      for k in range(s,val-1,-1):
        dp[i][j][k]=dp[i-1][j][k]
        dp[i][j][k]+=dp[i-1][j-1][k-val]
      for k in range(val-1,-1,-1):
        dp[i][j][k]=dp[i-1][j][k]
  ans=0
  for i in range(1,n+1):
    ans+=dp[n][i][s]*pow(2,n-i,mod)
    ans%=mod
  print(ans)
calc()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))

    # 和がSとなるように選択する
    # DP[i][wa] ... i文字目まで見て和がwaとなる個数
    # DP = [[0]*(S+1) for i in range(N+1)]
    # DP[0][0] = 1
    # for i in range(1, N+1):
    #     DP[i][0] = 1
    #     for wa in range(S+1):
    #         DP[i][wa] = DP[i-1][wa]
    #         if 0 <= wa-A[i-1] <= S:
    #             DP[i][wa] += DP[i-1][wa-A[i-1]]
    #             DP[i][wa] %= MOD
    DP = [0]*(S+1)
    DP[0] = 1
    DP_new = DP[:]
    for i in range(N):
        for wa in range(S+1):
            if 0 <= wa-A[i] <= S:
                DP_new[wa] += DP[wa-A[i]]
                DP_new[wa] %= MOD
        DP = DP_new

    # print(*DP, sep="\n")

    # 組み合わせはDP[N][S]個存在する。
    # DPを逆に辿って集合を得る
    # 集合を含むような部分集合を数えあげる

    @lru_cache(maxsize=None)
    def reconstruct(n, wa):
        # nまで見て、和がwaとなるような集合のリストを返す
        # print("(n, wa)", n, wa)
        ans = []
        if wa < 0 or n < 0 or DP[n][wa] == 0:
            # print("?")
            return ans
        if n-1 >= 0 and DP[n-1][wa] != 0:
            ans.extend(reconstruct(n-1, wa))
        if DP[n][wa] != DP[n-1][wa]:
            # 文字の追加がある
            if wa-A[n-1] == 0:
                # print("only")
                ans.append({n-1})
            else:
                # print("add")
                if n-1 >= 0 and DP[n-1][wa-A[n-1]] != 0:
                    b = reconstruct(n-1, wa-A[n-1])
                    ans.extend([bb | {n-1} for bb in b])
        # print("ret, ", ans)
        return ans

    ans = 0
    for s in reconstruct(N, S):
        ans += pow(2, N - len(s), MOD)
        ans %= MOD
    print(ans)

    return


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, []] for i 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 - A[i]):
        if dp[i][j][0]:
            dp[i + 1][j] = dp[i][j]
            dp[i + 1][j + A[i]][0] += dp[i][j][0]
            dp[i + 1][j + A[i]][1] += list(map(lambda x: x + 1dp[i][j][1]))


ans = 0
for i in range(N + 1):
    ans += sum(dp[i][S][0])
    ans %= MOD

print(ans)

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) for _ in range(n+1)] for _ in range(n+1)]
  dp[0][0][0]=1
  for i in range(1,n+1):
    val=arr[i-1]
    for j in range(i,-1,-1):
      for k in range(s,val-1,-1):
        dp[i][j][k]=dp[i-1][j][k]%mod
        dp[i][j][k]+=dp[i-1][j-1][k-val]
      for k in range(val-1,-1,-1):
        dp[i][j][k]=dp[i-1][j][k]%mod
  ans=0
  for i in range(1,n+1):
    ans+=dp[n][i][s]*pow(2,n-i,mod)
    ans%=mod
  print(ans)
calc()

Submission status: Runtime Error

Solution code:
n,s=map(int,input().split())
mod=998244353
A=list(map(int,input().split()))
dp=[[]*(s+1) for i in range(n+1)]
dp[0][0]=[1]
for i in range(n+1):
  dp[i][0]=[1]
for i in range(1,n+1):
  for j in range(1,s+1):
    dp[i][j].append(dp[i-1][j])
    if j+A[i]<=s:
      dp[i][j+A[i]].append(dp[i][j]+1)
ans=0
for i in range(len(dp[n][s])):
  ans=ans+dp[n][s][i]*pow(2,n-i,mod)
print(ans%mod)

Submission status: Runtime Error

Solution code:
import copy

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

sa = sorted(a)

nums = [[] for _ in range(s+1)]
for i in range(n):
  nn = copy.deepcopy(nums)
  for j in range(s+1):
    for k in range(len(nums[j])):
      #print(j)
      #print(sa[i])
      #print(k)
      if j+sa[i]<=s:
        nums[j+sa[i]].append(nn[j][k]+1)
  if sa[i]<=s:
    nums[sa[i]].append(1)

  print(nums)

ans = 0
for v in nums[s]:
  ans += 2**(n-v)
  ans = ans%998244353

print(ans)

Submission status: Runtime Error

Solution code:
n, s = map(int, input().split())
listA = list(map(int, input().split()))

map = {}
def dp(currentL, sum, choice, l):
    key = str(len(currentL))+" "+str(sum)+" "+str(choice)
    if key in map:
        return map[key]
    elif sum < 0:
        map[key] = 0
        return 0
    elif sum == 0:
        map[key] = 2**(l-choice)
        return map[key]
    elif len(currentL) < 1:
        map[key] = 0
        return 0
    elif len(currentL)==1:
        if sum == currentL[0]:
            choice+=1
            map[key] = 2**(l-choice)
            return map[key]
        else:
            map[key] = 0
            return 0
    else:
        newL = currentL[1:]
        map[key] = dp(newL, sum, choice, l) % 998244353 + \
            dp(newL, sum-currentL[0], choice+1, l) % 998244353
        return map[key]


print(dp(listA, s, 0, len(listA)) % 998244353)

Submission status: Runtime Error

Solution code:
N,S = list(map(int,input().split()))
A = list(map(int,input().split()))
n = N
k = S
C = []

def bubunnwa(i,sum,b):
    if(i < n):
        b.append(0)
        bubunnwa(i+1,sum,b)
        del b[i:]
        b.append(1)
        bubunnwa(i+1,sum+A[i],b)
    elif(i == n and sum == k):
        C.append(b.copy())

bubunnwa(0,0,[])
ans = 0
for c in C:
    kazu = 0
    for cc in c:
        if cc == 1:
            kazu += 1
    ans += 2 ** (N - kazu)
ans = ans % 998244353
print(ans)

Submission status: Runtime Error

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp =[[0]*(S+1) for _ in range(N+1)]
for i in range(N+1):
    for j in range(S+1):
        if j ==0:
            dp[i][j] = [0]
        else:
            dp[i][j] = []
for i in range(1, N+1):
    a = A[i-1]
    for j in range(S+1):
        d = dp[i-1][j-a]
        if ((a<=S and j >= a) and d != []):
            add = []
            for k in d:
                add.append(k+1)
            dp[i][j] = add+dp[i-1][j]
        else:
            dp[i][j] = dp[i-1][j]
ans = 0
sq = [1]
for i in range(N):
    sq.append(sq[-1]*2)
for i in dp[N][S]:
    ans = (ans+sq[N-i])%998244353
print(ans)

Submission status: Runtime Error

Solution code:
n,s=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
    if a[i]>n:
        a.remove(i)
b=list()
for i in range(n):
    b.append(0)
now=0
weight=0
ans=0
while True:
    if now>=n:
        if not 1 in b:
            break
        else:
            idx="".join(map(str,b)).rfind("1")
            b[idx]=0
            now=idx+1
            weight-=a[idx]
            continue
    if weight+a[now]<s:
        b[now]=1
        weight+=a[now]
        now+=1
        continue
    elif weight+a[now]==s:
        x=n-sum(b)-1
        y=1
        for i in range(x):
            y*=2
            y=y%998244353
        ans+=y
        now+=1
    else:
        now+=1
        
print(ans%998244353)

Submission status: Runtime Error

Solution code:
def get_integral_value_combination(list, target):
    def a(idx, l, r, t):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(list)):
            a((u + 1), l + [list[u]], r, t)
        return r
    return a(0, [], [], target)
N, S = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
ans = 0
ind = get_integral_value_combination(A, S)
for i in ind:
    ans += 2 ** (N - len(i))
ans %= 998244353
print(ans)

Submission status: Runtime Error

Solution code:
n, s = map(int, input().split())
listA = list(map(int, input().split()))

map = {}
def dp(currentL, sum, choice, l):
    key = str(len(currentL))+" "+str(sum)+" "+str(choice)
    if key in map:
        return map[key]
    elif sum < 0:
        map[key] = 0
        return 0
    elif sum == 0:
        map[key] = 2**(l-choice)
        return map[key]
    elif len(currentL)==1:
        if sum == currentL[0]:
            choice+=1
            map[key] = 2**(l-choice)
            return map[key]
        else:
            map[key] = 0
            return 0
    else:
        newL = currentL[1:]
        map[key] = dp(newL, sum, choice, l) % 998244353 + \
            dp(newL, sum-currentL[0], choice+1, l) % 998244353
        return map[key]


print(dp(listA, s, 0, len(listA)) % 998244353)

Submission status: Runtime Error

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp =[[0]*(S+1) for _ in range(N+1)]
for i in range(N+1):
    for j in range(S+1):
        if j ==0:
            dp[i][j] = [0]
        else:
            dp[i][j] = []
for i in range(1, N+1):
    a = A[i-1]
    for j in range(S+1):
        d = dp[i-1][j-a]
        if a<=S and j >= a and d != []:
            add = []
            for k in d:
                add.append(k+1)
            dp[i][j] = add+dp[i-1][j]
        else:
            dp[i][j] = dp[i-1][j]
ans = 0
sq = [1]
for i in range(N):
    sq.append(sq[-1]*2)
for i in dp[N][S]:
    ans = (ans+sq[N-i])%998244353
print(ans)

Submission status: Runtime Error

Solution code:
n, s = map(int, input().split())
listA = list(map(int, input().split()))

map = {}
def dp(currentL, sum, choice, l):
    key = str(len(currentL))+" "+str(sum)+" "+str(choice)
    if key in map:
        return map[key]
    elif sum == 0:
        map[key] = 2**(l-choice)
        return map[key]
    elif len(currentL)==1:
        if sum == currentL[0]:
            choice+=1
            map[key] = 2**(l-choice)
            return map[key]
        else:
            map[key] = 0
            return 0
    else:
        newL = currentL[1:]
        map[key] = dp(newL, sum, choice, l) % 998244353 + \
            dp(newL, sum-currentL[0], choice+1, l) % 998244353
        return map[key]


print(dp(listA, s, 0, len(listA)) % 998244353)

Submission status: Runtime Error

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp =[[0]*(S+1) for _ in range(N+1)]
for i in range(N+1):
    for j in range(S+1):
        if j ==0:
            dp[i][j] = [0]
        else:
            dp[i][j] = []
for i in range(1, N+1):
    a = A[i-1]
    for j in range(S+1):
        d = dp[i-1][j-a]
        if a<=S and j >= a and d != []:
            add = []
            for k in d:
                add.append(k+1)
            dp[i][j] = add+dp[i-1][j]
        else:
            dp[i][j] = dp[i-1][j]
ans = 0
sq = [1]
for i in range(N):
    sq.append(sq[-1]*2)
for i in dp[N][S]:
    ans = ans+sq[N-i]
print(ans%998244353)

Submission status: Runtime Error

Solution code:
n, s = map(int, input().split())
listA = list(map(int, input().split()))

map = {}
def dp(currentL, sum, choice, l):
    key = str(len(currentL))+" "+str(sum)+" "+str(choice)
    if key in map:
        return map[key]
    if sum == 0:
        map[key] = 2**(l-choice)
        return map[key]
    elif len(currentL)==1:
        if sum == currentL[0]:
            choice+=1
            map[key] = 2**(l-choice)
            return map[key]
        else:
            map[key] = 0
            return 0
    else:
        newL = currentL[1:]
        map[key] = dp(newL, sum, choice, l) % 998244353 + \
            dp(newL, sum-currentL[0], choice+1, l) % 998244353
        return map[key]


print(dp(listA, s, 0, len(listA)) % 998244353)

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
from functools import lru_cache
mod = 998244353

def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))

    @lru_cache(maxsize=None)
    def g(n, S):
        if S == 0: return pow(2, n + 1, mod) - 1
        if n == 0 and S == A[0]: return 1
        if n == 0: return 0
        val = (g(n - 1, S) * 2 + g(n - 1, S - A[n])) % mod
        if A[n] == S: val += 1
        #print("g({},{})={}".format(n, S, val))
        return val % mod
    
    print(g(N - 1, S))

    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,s,*a=map(int,open().read().split());d=[0]*-~s;m=998244353;v=pow(2,m-2,m);d[0]=pow(2,n,m)
for i in a:
  for j in range(s,i-1,-1):d[j]+=(d[j-i]*v)%m
print(d[s])

Submission status: Runtime Error

Solution code:
n, s = map(int, input().split())
a = list(map(int, input().split()))

mod = 998244353

dp = [[0] * (n + 1) for _ in range(s + 1)]

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % mod
        x *= x % mod
        n //= 2

    return K * x % mod

inv2 = pow_k(2, mod - 2)
pow2n = pow_k(2, n)

dp[0][0] = pow2n
for i in range(1, n + 1):
    for j in range(s + 1):
        if j >= a[i - 1]:
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - a[i - 1]] * inv2 % mod) % mod
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[n][s])

Submission status: Runtime Error

Solution code:
from collections import Counter

MOD = 998244353

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

dks = [[None for s_ in range(s + 1)] for i in range(n)]


def getks(i=0, s=s):
    # la[i:]
    if s < 0:
        return Counter({})
    elif i == n:
        if s == 0:
            return Counter({0: 1})
        else:
            return Counter({})
    elif dks[i][s] is not None:
        return dks[i][s]
    else:
        ks0 = getks(i + 1, s)
        ks1 = Counter({
            k + 1: v for k, v in
            getks(i + 1, s - la[i]).items()
        })
        ks = ks0 + ks1

        dks[i][s] = ks
        return ks


ks = getks()

answer = 0
for k, v in ks.items():
    answer += pow(2, n - k, MOD) * v
    answer %= MOD

print(answer)

Submission status: Runtime Error

Solution code:
n, s = map(int, input().split())
listA = list(map(int, input().split()))

def dp(currentL, sum, choice, l):
    if sum == 0:
        return 2**(l-choice)
    elif len(currentL)==1:
        if sum == currentL[0]:
            choice+=1
            return 2**(l-choice)
        else:
            return 0
    else:
        newL = currentL[1:]
        return dp(newL, sum, choice, l) % 998244353+dp(newL, sum-currentL[0], choice+1, l) % 998244353


print(dp(listA, s, 0, len(listA)) % 998244353)

Submission status: Runtime Error

Solution code:
N,S=map(int,input().split())
A=list(map(int,input().split()))
#dp[i]{:}:iまでを使って数字k個でjを作る方法
dp=[[{}]*(S+1) for _ in range(N+1)]
dp[0][0]={0:1}
for i in range(1,N+1):
  for j in range(S):
    if j+A[i]>S:
      break()
    for k,v in dp[i-1][j].items:
      dp[i][j+A[i]][k+1]+=v

print(dp[N][K])

Submission status: Runtime Error

Solution code:
n, s = map(int, input().split())
listA = list(map(int, input().split()))

def dp(currentL, sum, choice, l):
    if sum == 0:
        return 2**(l-choice)
    elif len(currentL)==1:
        if sum == currentL[0]:
            choice+=1
            return 2**(l-choice)
        else:
            return 0
    else:
        newL = currentL[1:]
        return dp(newL, sum, choice, l)+dp(newL, sum-currentL[0], choice+1, l)


print(dp(listA, s, 0, len(listA)) % 998244353)

Submission status: Runtime Error

Solution code:
def subsets(nums):
    output = []
    for i in range(1, len(nums)):
        backtrack(0, nums, i, [], output)

    return output


def backtrack(start, nums, size, curr, output):
    if len(curr) == size:
        output.append(curr[:])

    for i in range(start, len(nums)):
        curr.append(nums[i])
        backtrack(i + 1, nums, size, curr, output)
        curr.pop()


def count_subsets(num, sum):
    n = len(num)
    dp = [0 for _ in range(sum+1)]
    dp[0] = 1

    for s in range(1, sum+1):
        dp[s] = 1 if num[0] == s else 0

    for i in range(1, n):
        for s in range(sum, -1, -1):
            if s >= num[i]:
                dp[s] += dp[s - num[i]]

    return dp[-1]


N, S = map(int, input().split())
sub_sets = list(map(int, input().split()))
seen = {}

result = count_subsets(sub_sets, S)

if result == 0:
    print(0)
    exit()

new_subsets = subsets(sub_sets)

for sets in new_subsets:
    if sets in seen:
        result += seen[sets]
    else:
        total_pattern = count_subsets(sets, S)
        seen[sets] = total_pattern
        result += total_pattern

print(result % 998244353)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef vector<vector<int>> vv;
typedef pair<int, int> P;


int N, S;
vector<ll> A;
map<ll, map<ll, ll>> m;
const ll MOD = 998244353;


void input() {
    cin >> N >> S;
    A = vector<ll>(N);
    rep(i, N) cin >> A[i];
}


int main() {
    input();
    m[0][0] += 1;
    for (int a : A) {
        for (int i = S - a; i >= 0; i--) {
            if (!m.count(i)) continue;
            for (auto p : m[i]) {
                m[a + i][p.first + 1] += p.second;
                m[a + i][p.first + 1] %= MOD;
            }
        }
    }

    vector<ll> p2(3001);
    p2[0] = 1;
    rep(i, 3000) p2[i + 1] = p2[i] * 2 % MOD;
    ll ans = 0;
    for (auto p : m[S]) {
        if (p.first == 0) continue;
        ll v = p.second * p2[N - p.first] % MOD;
        ans = (ans + v) % MOD;
    }
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit=10**8
mod=998244353
n,s=map(int,input().split())
a=list(map(int,input().split()))
ans=0
l=0
from functools import lru_cache
# @lru_cache(maxsize=None)
def dfs(x,y):
	global l
	global ans
	if y==s:
		ans+=pow(2,n-l,mod)
		ans%=mod
		return
	elif y>s or x==n:
		return
	l+=1
	dfs(x+1,y+a[x])
	l-=1
	dfs(x+1,y)
dfs(0,0)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(5000)
MOD=998244353
def dfs(d,tot,num):
    global A,N,S,how
    if tot==S:
        how[num]+=1
        return
    if d==N:
        return
    if d>0 and A[d]==A[d-1]:
    if tot+A[d]<=S:
        dfs(d+1,tot+A[d],num+1)
        dfs(d+1,tot,num)
        
    

N,S=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
how=[0]*(N+1)
dfs(0,0,0)
cur=1
res=0
for i in range(N,0,-1):
    res+=(how[i]*cur)%MOD
    cur=cur*2%MOD
print(res)

Submission status: Runtime Error

Solution code:
n,s = map(int,input().split())
a = list(map(int,input().split()))

mod = 998244353

dp = [[0]*s for _ in range(n)]

for i in range(n):
    if a[i]-1 < n:
        dp[i][a[i]-1] += 2**i
        dp[i][a[i]-1] %= mod

for i in range(n):
    for j in range(s):
        if i != n-1:
            dp[i+1][j] += dp[i][j] * 2
            dp[i+1][j] %= mod
        if i != n-1 and 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[-1][-1]%mod)

Submission status: Runtime Error

Solution code:
import numpy as np

n, s = map(int, input().split())
A = list(map(int, input().split()))
DP = np.zeros(3001, dtype=np.int64)

for num, a in enumerate(A):
    double = DP * 2
    shift = np.hstack([np.zeros(a), DP[:-a]]).astype(np.int64)
    DP = double + shift
    DP[a] += 2 ** num

print(DP[s])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys
from typing import Tuple, Dict

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62

MOD = 998244353  # type: int
import numpy

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')


    @cc.export('s', '(i8[:],i8[:],i8)')
    def s(A: numpy.array, S: int, N: int):
        d: Dict[Tuple[int, int], int] = dict()
        ans = 0
        d[0, 0] = 1  # left:vale right:count
        for i, a in enumerate(A):
            for (left, right) in sorted(d.keys(), reverse=True):
                if left + a > S:
                    continue
                if (left + a, right + 1) in d:
                    d[left + a, right + 1] += d[left, right]
                else:
                    d[left + a, right + 1] = d[left, right]
        for val, count in d:
            if val != S:
                continue
            ans += d[val, count] * 2 ** (N - count)
            ans %= 998244353
        return ans


    cc.compile()
    exit(0)

from my_module import s


def solve(N: int, S: int, A: "List[int]"):
    A.sort()
    print(s(numpy.array(A), S, N))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, S, (A))


if __name__ == '__main__':
    main()