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

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

mod = 998244353

pows = [1]
for i in range(10000):
    pows.append((pows[-1] * 2) % mod)

dp = [0] * (s + 1)
dp[0] = 1
if a[0] <= s:
    dp[a[0]] = 1

for i in range(1, n):
    dp_new = [0] * (s + 1)
    dp_new[0] = 1
    for j in range(1, s + 1):
        dp_new[j] = dp[j] * 2

        if j - a[i] > 0:
            dp_new[j] += dp[j-a[i]]
        elif j == a[i]:
            dp_new[j] += pows[i]
        dp_new[j] %= mod

    dp = dp_new

print(dp[-1])

Solution (Python):
N, S = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
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]
        dp[i + 1][j] %= mod 
        if j + A[i] <= S : 
            dp[i + 1][j + A[i]] += dp[i][j]
            dp[i + 1][j + A[i]] %= mod
print(dp[N][S])

Solution (Python):
import numpy as np

def main():
    n, s = map(int, input().split())
    a = [int(i) for i in input().split()]
    mod = 998244353
    dp = np.zeros((n + 1, s + 1), dtype=int)
    dp[0][0] = 1
    for i in range(n):
        ai = a[i]
        dp[i + 1] = dp[i] * 2 % mod
        dp[i + 1, ai:] = (dp[i + 1, ai:] + dp[i, :-ai]) % mod
    print(dp[n][s])

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

mod = 998244353

n, s = map(int, input().split())
A = list(map(int, input().split()))
DP = np.zeros(3005, dtype=np.int64)
DP[0] = 1

for a in A:
    double = DP * 2
    double[a:] += DP[:-a]  
    DP = double % mod

print(DP[s])

Solution (Python):
def main():
    n, s = map(int, input().split())
    a = [int(i) for i in input().split()]
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        ai = a[i]
        for j in range(s + 1):
            if j < ai:
                dp[i + 1][j] = dp[i][j] * 2 % 998244353
            else:
                dp[i + 1][j] = (dp[i][j] * 2 + dp[i][j - ai]) % 998244353
    print(dp[n][s])

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

mod = 998244353

n, s = map(int, input().split())
A = list(map(int, input().split()))
DP = np.zeros(3005, dtype=np.int64)
DP[0] = 1

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

print(DP[s])

Solution (Python):
def main():
    n, s = map(int, input().split())
    a = sorted([int(i) for i in input().split()])
    mod = 998244353
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        ai = a[i]
        for j in range(s + 1):
            if j < ai:
                dp[i + 1][j] = dp[i][j] * 2 % mod
            else:
                dp[i + 1][j] = (dp[i][j] * 2 % mod + dp[i][j - ai]) % mod
    print(dp[n][s])

if __name__ == '__main__':
    main()

Solution (Python):

ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import math
import itertools
gcd = math.gcd
mod = 998244353
n,s = ma()
A = list(ma())
dp = [[0]*(s+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(n):
    a = A[i]
    for j in range(s+1):
        dp[i+1][j] =(dp[i][j]*2)%mod
        if a<=j:
            dp[i+1][j] = (dp[i][j-a] +dp[i+1][j]) %mod

print(dp[n][s])

Solution (Python):
n,s=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
ans=0
dp=[[0 for _ in range(s+1)] for _ in range(n+1)]
dp[0][0]=1

for i in range(n):
    for c in range(s+1):
        if c>=A[i]:
            dp[i+1][c]=(2*dp[i][c]+dp[i][c-A[i]])%mod
        else:
            dp[i+1][c]=(2*dp[i][c])%mod

print(dp[n][s]%mod)

Solution (Python):
n, s = map(int, input().split())
a = sorted(list(map(int, input().split())))
mod = 998244353

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

for i in range(1, n+1):
    for j in range(s+1):
        dp[i][j] += 2 * dp[i-1][j]
        dp[i][j] %= mod

        if j + a[i-1] <= s:
            dp[i][j+a[i-1]] += dp[i-1][j]
            dp[i][j+a[i-1]] %= mod

print(dp[-1][-1])

Solution (Python):
import numpy as np
N,S=map(int,input().split())
As=list(map(int,input().split()))

MOD=998244353


d=np.zeros((3001,3001))
d[0,0]=1

for i in range(1,N+1):
    Ai=As[i-1]
    d[i] += 2*d[i-1]
    d[i,Ai:] += d[i-1][:-Ai]
    d[i] %= MOD
print(int(d[N][S]))

Solution (Python):
mod = 998244353

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

dp = [[0 for _ in range(s + 1)] for _ in range(n + 1)]
dp[0][0] = 1
for i, num in enumerate(a, start = 1):
    for j in range(s + 1):
        dp[i][j] = (dp[i - 1][j] * 2) % mod
        if j - num >= 0:
            dp[i][j] += dp[i - 1][j - num]

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

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

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

if __name__ == "__main__":
  main()

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 998244353

N, K = MAP()
A = LIST()

dp = list2d(N+1, K+1, 0)
dp[0][0] = 1
for i, a in enumerate(A):
    for j in range(K+1):
        dp[i+1][j] += dp[i][j] * 2
        dp[i+1][j] %= MOD
        if j+a <= K:
            dp[i+1][j+a] += dp[i][j]
            dp[i+1][j+a] %= MOD
ans = dp[N][K]
print(ans)

Solution (Python):



import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
from itertools import accumulate, combinations
input = sys.stdin.readline

mod = 998244353

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

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

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


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

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np

MOD = 998244353
n, s = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
dp = np.zeros(s+1, dtype=np.int64)
dp[0] = 1
for a in A:
  t = dp.copy() * 2
  t[a:] += dp[:-a]
  t %= MOD
  dp = t
ans = dp[s]
print(ans)

Solution (Python):
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1

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

Solution (Python):
MOD=998244353
n,s=map(int,input().split())
a=list(map(int,input().split()))
al=sum(a)
dp=[[0]*3001 for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    for j in range(3001):
        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])

Solution (Python):




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

mod = 998244353

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

dp[0][0] = 1

for i in range(0, n):
    for j in range(0, s+1):
        dp[i+1][j] += dp[i][j]*2 % mod

        if j+a[i] <= s:
            dp[i + 1][j + a[i]] += dp[i][j] % mod


print(dp[n][s] % mod)

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

DP = [[0] * (S + 1) for i in range(N + 1)]
DP[0][0] = 1
for i in range(N):
  for j in range(S + 1):
    if j >= A[i]:
      DP[i + 1][j] = (DP[i][j] * 2 + DP[i][j - A[i]]) % MOD
    else:
      DP[i + 1][j] = (DP[i][j] * 2) % MOD

print(DP[-1][-1] % MOD)

Solution (Python):
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

n, s = nm()
a = nl()
mod = 998244353
dp = [0]*(s+1)
dp[0] = 1
for i in range(n):
    v = a[i]
    for j in range(s, -1, -1):
        if j >= v:
            dp[j] = (dp[j] * 2 + dp[j-v]) % mod
        else:
            dp[j] = dp[j] * 2 % mod
print(dp[s])

Solution (Python):
import numpy as np

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

MOD = 998244353

dp = np.zeros(S + 1, dtype=int)
dp[0] = 1

for i in A:
    ep = dp * 2
    ep[i:] += dp[:-i]
    dp = ep % MOD

print(dp[S])

Solution (Python):
def main():
  n, s = map(int, input().split())
  a = [int(x) for x in input().split()]
  mod = 998244353
  
  dp = [[0]*(s+1) for _ in range(n+1)]
  dp[0][0] = 1
  for i in range(1, n+1):
    for j in range(s, -1, -1):
      dp[i][j] += dp[i-1][j]*2
      dp[i][j] %= mod
      if dp[i-1][j] and j+a[i-1] <= s:
        dp[i][j+a[i-1]] += dp[i-1][j]
        dp[i][j+a[i-1]] %= mod

  print(dp[n][s])
  
  
if __name__ == "__main__":
  main()

Solution (Python):
import numpy as np

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

MOD = 998244353

dp = np.zeros(S + 1, dtype=int)
dp[0] = 1

for i in A:
    ep = dp.copy()
    ep += dp
    ep[i:] += dp[:-i]
    dp = ep % MOD

print(dp[S])

Solution (Python):
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
MOD = 998244353
for i in range(n):
    for j in range(s+1):
        dp[i+1][j] = dp[i][j]*2
        if a[i] <= j:
            dp[i+1][j] += dp[i][j-a[i]]
        dp[i+1][j] %= MOD
print(dp[n][s])

Solution (Python):
N,S = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
dp = [ [0]*(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]
    dp[i+1][j] %= mod
    if j+A[i] <= S:
      dp[i+1][j+A[i]] += dp[i][j]
      dp[i+1][j+A[i]] %= mod

print(dp[N][S])

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

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

dp[0][0] = 1

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

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

    
    
    INF = 10**10  
    MOD=998244353
    
    I, J =N,S
    
    dp = [[0]*(J+1) for _ in range(I+1)]
    
    dp[0][0] = 1
    
    for i in range(I):
        for j in range(J+1):
            dp[i+1][j]+=2*dp[i][j]
            dp[i+1][j]%=MOD
            if j+A[i]<=S:
                dp[i+1][j+A[i]]+=dp[i][j]
                dp[i+1][j+A[i]]%=MOD

    print(dp[I][J])
    
    
    
resolve()

Solution (Python):
def main():
    N, S = map(int, input().split())
    A = tuple(map(int, input().split()))

    MOD = 998244353

    dp = [[0]*(S+1) for _ in range(N+1)]
    dp[0][0] = 1
    
    for i, a in enumerate(A):            
        for j in range(S+1):
            if j >= a:
                dp[i+1][j] = 2 * dp[i][j]
                dp[i+1][j] %= MOD
                dp[i+1][j] += dp[i][j-a]
                dp[i+1][j] %= MOD
            else:
                dp[i+1][j] = 2 * dp[i][j]
                dp[i+1][j] %= MOD
                

    print(dp[N][S])
if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import defaultdict
input = sys.stdin.readline
mod = 998244353
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return ( m + x%m ) % m
def main():
    n,s = map(int,input().split())
    a = list(map(int, input().split()))
    dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
    dp[0][0] = pow(2,n,mod)
    MODINV2 = mod_inv(2,mod)
    ans = 0
    for i in range(n):
        for j in range(s,-1,-1):
            if j-a[i] < 0:
                continue
            dp[i+1][j] += dp[i][j-a[i]]*MODINV2
            dp[i+1][j] %= mod
        for j in range(s,-1,-1):
            if j == s:
                ans += dp[i+1][j]
                ans %= mod
            else:
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= mod
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
N,S = map(int,input().split())

A = list(map(int,input().split()))
MOD = 998244353
dp = [0 for _ in range(S+1)]

dp[0] = 1


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

Solution (Python):
import numpy as np

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

dp = np.zeros(s + 1, np.int64)
dp[0] = 1

for e in a:
    pre = dp.copy()
    dp = pre * 2
    dp[e:] += pre[:-e]
    dp %= mod

ans = dp[s]
print(ans)

Solution (Python):
def main():
    N, S = map(int, input().split())
    A = tuple(map(int, input().split()))

    MOD = 998244353

    dp = [[0]*(S+1) for _ in range(N+1)]
    dp[0][0] = 1
    
    for i, a in enumerate(A):
        dp[i][0] = pow(2, i, MOD)
            
        for j in range(S+1):
            if j >= a:
                dp[i+1][j] = 2 * dp[i][j]
                dp[i+1][j] %= MOD
                dp[i+1][j] += dp[i][j-a]
                dp[i+1][j] %= MOD
            else:
                dp[i+1][j] = 2 * dp[i][j]
                dp[i+1][j] %= MOD
                

    print(dp[N][S])
if __name__ == "__main__":
    main()

Solution (Python):
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))
dp = [[0 for _ in range(S+1)] for _ 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]
    dp[i+1][j] %= mod
    if j + A[i] <=S:
      dp[i+1][j+A[i]] += dp[i][j]
      dp[i+1][j+A[i]] %= mod
print(dp[N][S]%mod)

Solution (Python):
mod = 998244353

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

a.sort()

while a[-1] > s:
    a.pop(-1)
    if a == []:
        print(0)
        exit()

dp = [0] * (s + 1)
dp[0] = 1
for i in a:
    newdp = [2 * j % mod for j in dp]
    for j in range(s - i + 1):
        newdp[j+i] += dp[j]
    dp = newdp

print(dp[s] * pow(2, n - len(a), mod) % mod)

Solution (Python):
mod = 998244353

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

a.sort()

while a[-1] > s:
    a.pop(-1)
    if a == []:
        print(0)
        exit()

dp = [0] * (s + 1)
dp[0] = 1
for i in a:
    newdp = [2 * j for j in dp]
    for j in range(s - i + 1):
        newdp[j+i] += dp[j]
    dp = newdp

print(dp[s] * pow(2, n - len(a), mod) % mod)

Solution (Python):
mod = 998244353

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

a.sort()

while a[-1] > s:
    a.pop(-1)
    if a == []:
        print(0)
        exit()

su = sum(a)
if su < s:
    print(0)
    exit()
if su == s:
    print(pow(2, n - len(a), mod))
    exit()

dp = [0] * (s + 1)
dp[0] = 1
for i in a:
    newdp = [2 * j for j in dp]
    for j in range(s - i + 1):
        newdp[j+i] += dp[j]
    dp = newdp

print(dp[s] * pow(2, n - len(a), mod) % mod)

Solution (Python):
def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 998244353
    dp = [[0] * (S+5) for _ in range(N+5)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(S+1):
            dp[i+1][j] += 2 * dp[i][j]
            dp[i+1][j] %= MOD
            if j + A[i] <= S:
                dp[i+1][j+A[i]] += dp[i][j]
                dp[i+1][j+A[i]] %= MOD
    print(dp[N][S])



if __name__ == "__main__":
    main()

Solution (Python):
N, S = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
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]
        dp[i + 1][j] %= mod 
        if j + A[i] <= S : 
            dp[i + 1][j + A[i]] += dp[i][j]
            dp[i + 1][j + A[i]] %= mod
print(dp[N][S])

Solution (Python):
def DP(A,N,S,M):
    dp = [[0 for _ in range(S+1)] for _ in range(N+1)]
    dp[0][0] = 1
    
    for i in range(1,N+1):
        for j in range(S+1):
            dp[i][j] = 2 * dp[i-1][j]
            dp[i][j] %= M
            if j - A[i-1] >= 0:
                dp[i][j] += dp[i-1][j-A[i-1]]
                dp[i][j] %= M

    return dp[N][S]

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

    ans = DP(A,N,S,M)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
MOD = 998244353
def main():
    input = sys.stdin.readline
    N, S = map(int, input().split())
    *A, = map(int, input().split())
    
    dp = [[0] * (S + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(1, N + 1):
        a = A[i - 1]
        for k in range(S + 1):
            
            dp[i][k] = (dp[i][k] + dp[i - 1][k] * 2) % MOD
            
            if k >= a:
                dp[i][k] = (dp[i][k] + dp[i - 1][k - a]) % MOD
    print(dp[N][S])

if __name__ == '__main__':
    main()

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S, A):
    mod = 998244353
    memo = [0] * (S+1)
    memo[0] = 1
    for a in A:
        nm = [2*memo[s] % mod for s in range(S+1)]
        for s in range(S+1-a):
                nm[s+a] += memo[s]
                nm[s+a] %= mod
        memo = nm

    return memo[S]


def main():
    N, S = read_int_n()
    A = read_int_n()
    print(slv(N, S, A))


if __name__ == '__main__':
    main()

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 998244353
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,S = LI()
    A = [0] + LI()
    dp = [[0] * (S+1) for _ in range(N+1)]
    dp[0][0] = pow(2,N,MOD)
    d2 = pow(2,MOD-2,MOD)
    for i in range(1,N+1):
        for j in range(0,S+1):
            if j >= A[i]:
                dp[i][j] = (dp[i-1][j] + dp[i-1][j-A[i]] * d2) % MOD
            else:
                dp[i][j] = dp[i-1][j]

    print(dp[-1][-1])

if __name__ == '__main__':
    main()

Solution (Python):
mod=998244353
n,s=map(int,input().split())
ar=list(map(int,input().split()))
dp=[0 for y in range(s+1)]
dp[0]=1
for i in range(n):
    for j in range(s,-1,-1):
        if j+ar[i]<=s:
            dp[j+ar[i]]=(dp[j]+dp[j+ar[i]])%mod
        dp[j]=(dp[j]*2)%mod
print(dp[s])

Solution (Python):
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def egcd(a: int, b: int):
    """
    A solution of ax+by=gcd(a,b). Returns
    (gcd(a,b), (x, y)).
    """
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x


def modinv(a: int, mod: int = 10**9 + 7):
    """
    Returns a^{-1} modulo m.
    """
    g, x, y = egcd(a, mod)
    if g > 1:
        raise Exception('{}^(-1) mod {} does not exist.'.format(a, mod))
    else:
        return x % mod


import numpy as np


def main():
    N, S = geta(int)
    A = list(geta(int))
    A.sort()
    mod = 998244353

    inv2 = modinv(2, mod)

    dp = np.zeros((N + 1, S + 1), dtype=np.int64)

    _t = pow(2, N, mod)
    dp[:, 0] = _t
    for i in range(1, N + 1):
        dp[i, :] = dp[i - 1, :]
        if A[i - 1] <= S:
            tmp = np.roll(dp[i - 1, :], A[i - 1])
            tmp[:A[i - 1]] = 0
            dp[i, :] += tmp * inv2
            dp[i, :] %= mod

    print(dp[N][S])


if __name__ == "__main__":
    main()

Solution (Python):
MOD = 998244353
N,S = map(int,input().split())
A = list(map(int,input().split()))
dp = [[0]*(S+1) for _ 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]]
        dp[i+1][j] %= MOD


print(dp[N][S])

Solution (Python):
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def egcd(a: int, b: int):
    """
    A solution of ax+by=gcd(a,b). Returns
    (gcd(a,b), (x, y)).
    """
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x


def modinv(a: int, mod: int = 10**9 + 7):
    """
    Returns a^{-1} modulo m.
    """
    g, x, y = egcd(a, mod)
    if g > 1:
        raise Exception('{}^(-1) mod {} does not exist.'.format(a, mod))
    else:
        return x % mod


def main():
    N, S = geta(int)
    A = list(geta(int))
    A.sort()
    mod = 998244353

    inv2 = modinv(2, mod)

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

    _t = pow(2, N, mod)
    for n in range(N + 1):
        dp[n][0] = _t

    for i in range(1, N + 1):
        for j in range(1, S + 1):
            if j >= A[i - 1]:
                dp[i][j] = dp[i - 1][j - A[i - 1]] * inv2 + dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j]

            dp[i][j] %= mod

    print(dp[N][S])


if __name__ == "__main__":
    main()

Solution (Python):

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

    dp = [[0] * (S + 1) for _ 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]
            dp[i + 1][j] %= MOD
            if j + A[i] <= S:
                dp[i + 1][j + A[i]] += dp[i][j]
                dp[i + 1][j + A[i]] %= MOD
    print(dp[N][S])


if __name__ == "__main__":
    resolve()

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    MOD = 998244353
    N, S = map(int, rl().split())
    A = list(map(int, rl().split()))
    
    dp = [[0] * 3010 for _ in range(3010)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(S + 1):
            dp[i + 1][j] += 2 * dp[i][j]
            dp[i + 1][j] %= MOD
            if j + A[i] <= S:
                dp[i + 1][j + A[i]] += dp[i][j]
                dp[i + 1][j + A[i]] %= MOD
    print(dp[N][S])


if __name__ == '__main__':
    solve()

Solution (Python):
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[s]%mod)
calc()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
mod = 998244353

n,s = map(int,readline().split())
a = list(map(int,readline().split()))
d = np.zeros(3001, np.int64)
d[0] = 1
for i in a:
  dd = [0]*i + list(d)
  d = d*2
  d += dd[:3001]
  d %= mod
print(d[s])

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

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









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

print(dp[N][S])

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

dp = [[0]*(S+1) for i in range(N+1)]
dp[0][0] = 1
for i, a in  enumerate(A, 1):
  for s in range(S+1):
    dp[i][s] = 2*dp[i-1][s]
    if a <= s:
      dp[i][s] += dp[i-1][s-a]
    dp[i][s] %= MOD

print(dp[-1][-1])

Solution (Python):
import sys
import math
def input():
    return sys.stdin.readline()[:-1]
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(1,n+1):
    for j in range(s+1):
        if j-a[i-1]>=0:
            dp[i][j] += dp[i-1][j-a[i-1]]
            dp[i][j] %= mod

        dp[i][j] += dp[i-1][j]*2
        dp[i][j] %= mod

print(dp[n][s])

Solution (Python):
mod = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
    dp[i][0] = dp[i-1][0]*2%mod

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

ans = dp[-1][-1]%mod
print(ans)

Solution (Python):
n,s = map(int,input().split())
a = list(map(int,input().split()))
mod = 998244353
dp = [[0 for i in range(s+1)] for j in range(n+1)]
for i in range(n+1):
    dp[i][0] = 1
for i in range(1,n+1):
    x = a[i-1]
    for j in range(s+1):
        dp[i][j] = dp[i-1][j] * 2
        if dp[i][j] >= mod:
            dp[i][j] %= mod
    for j in range(x,s+1):
        if j >= x:
            dp[i][j] += dp[i-1][j-x]
            if dp[i][j] >= mod:
                dp[i][j] %= mod

print(dp[-1][-1])

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

if __name__=="__main__":
    main()

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

if __name__=="__main__":
    main()