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):
def examA():
    A, B = LI()
    ans = A*B
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    for a in A:
        if a==0:
            print(0)
            return
    ans = 1
    for a in A:
        ans *= a
        if ans>10**18:
            print(-1)
            return
    print(ans)
    return

def examC():
    A, B = LSI()
    ans =math.floor(int(A)*float(B))
    print(ans)
    return

def examD():
    def factorization(n):
        arr = defaultdict(int)
        temp = n
        for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
            if temp % i == 0:
                cnt = 0
                while temp % i == 0:
                    cnt += 1
                    temp //= i
                arr[i] = cnt
        if temp != 1:
            arr[temp] = 1
        if arr == []:
            arr[n] = 1
        return arr
    C = [0,1,3,6,10,15,21,28,36,45]
    N = I()
    F = factorization(N)
    ans = 0
    
    for f in F.values():
        for i in range(10):
            if C[i]>f:
                ans += i-1
                break
    print(ans)
    return

def examE():
    N = I()
    A = [0]*N
    B = [0]*N
    for i in range(N):
        A[i],B[i] = LI()
    A.sort()
    B.sort()
    if N%2==0:
        L = (A[N//2-1] + A[N//2])/2
        R = (B[N//2-1] + B[N//2])/2
        ans = int((R-L)*2) +1
    else:
        L = A[N//2]
        R = B[N//2]
        ans = (R-L)+1

    print(ans)
    return

def examF():
    inv = pow(2,mod2-2,mod2)
    N, S = LI()
    A = LI()
    dp = [[0]*(S+1)for _ in range(N+1)]
    dp[0][0] = pow(2,N,mod2)
    for i in range(N):
        a = A[i]
        for s in range(S+1):
            dp[i+1][s] += dp[i][s]
            dp[i+1][s] %= mod2
            if (s+a<=S):
                dp[i+1][s+a] += dp[i][s]*inv%mod2
                dp[i + 1][s+a] %= mod2
   
    ans = dp[-1][-1]%mod2
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<60
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 998244353

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, S = LI()
    a = LI()
    dp = [[0 for _ in range(S+1)] for _ in range(N+1)]
    for i in range(1, N+1):
        dp[i][0] = dp[i-1][0] * 2 + 1
        dp[i][0] %= mod
    for i in range(N):
        for j in range(1, S+1):
            if j - a[i] >= 0:
                dp[i+1][j] = (dp[i][j-a[i]] % mod) + (dp[i][j] * 2 % mod)
            else:
                dp[i+1][j] = dp[i][j] * 2 % mod
            if j == a[i]:
                dp[i+1][j] += 1
            dp[i+1][j] %= mod
    print(dp[N][S])

main()

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

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

mod = 998244353
l = 3050

M = [1]  
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  
    return pow(x, mod-2, mod)

D = [0] * 3050

M2 = [1]
M2I = [0] * l

for i in range(l-1):
    M2.append((M2[-1] * 2) % mod)
for i in range(l):
    M2I[i] = inv(M2[i], mod)

i2 = inv(2,mod)

D[0] = M2[n]
for i in range(n):
    for j in range(l-1,-1,-1):
        if j - A[i] >= 0:
            D[j] = (D[j] + D[j-A[i]] * i2) % mod
    
    
print(D[s])

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 998244353
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,S=LI()
DP = [[0 for i in range(S+1)] for j in range(N+1)]
LIS=LI()
DP[0][0]=1
for i in range(N):
    v = LIS[i]
    for j in range(S+1):
        if j-v >= 0:
            DP[i+1][j] = (2*DP[i][j] + DP[i][j-v])%DVSR
        else:
            DP[i+1][j] = (2*DP[i][j])%DVSR

print(DP[N][S])

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

print(dp[N][S])

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

twos = [1]*N
for i in range(1,N):
    twos[i] = (twos[i-1]*2)%p

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

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

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




for i in range(n):
    for j in range(s + 1):
        
        if j + a[i] <= s:
            dp[i + 1][1][j + a[i]] += dp[i][0][j] + dp[i][1][j]
            dp[i + 1][1][j + a[i]] %= MOD
        
        dp[i + 1][0][j] += (dp[i][0][j] + dp[i][1][j]) * 2
        dp[i + 1][0][j] %= MOD
ans = 0
for i in range(n + 1):
    ans += dp[i][1][-1] * pow(2, (n - i), MOD)
    ans %= MOD
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
from collections import deque,defaultdict
import heapq
from itertools import combinations
import bisect


mod=998244353
pp=pow(2,mod-2,mod)

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

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

for i in range(n):
    for j in range(s+1):
        if dp[i][j]>=1:
            if j+l[i]<=s:
                dp[i+1][j+l[i]]+=dp[i][j]*pp
                dp[i+1][j+l[i]]%=mod
            dp[i+1][j]+=dp[i][j]
            dp[i+1][j]%=mod
print(dp[-1][-1]%mod)

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

mod = 998244353

def power(n,e):
    ret = 1
    b = n
    while e:
        if e % 2 != 0:
            ret *= b
        ret %= mod
        b *= b
        b %= mod
        e //= 2
    return ret

def div(n1,n2):
    return n1*power(n2,mod-2)%mod

dp[0][0] = power(2,n)
for i in range(1,n+1):
    for j in range(s+1):
        dp[i][j] = dp[i-1][j] % mod
    for j in range(s+1):
        if j >= a[i-1]:
            dp[i][j] += div(dp[i-1][j-a[i-1]],2)

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

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

A = list(map(int, input().split()))
mod = 998244353

dp = [0] * (S+1)
dp[0] = 1

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

print(dp[S]%mod)

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

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

Solution (Python):
n,s = map(int,input().split())
a = list(map(int,input().split()))
if n == 1:
    if a[0] == s:
        print(1)
        quit()
    else:
        print(0)
        quit()

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

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

def solve(N, S, A):
    mod = 998244353
    dp = [0] * (S + 1)
    dp[0] = pow(2, N, mod)
    div2 = pow(2, mod - 2, mod)
    m = 0
    for a in A:
        m += a
        for i in reversed(range(a, min(S, m) + 1)):
            dp[i] = (dp[i] + dp[i - a] * div2) % mod
    return dp[S]

print(main())

Solution (Python):
import sys
input = sys.stdin.buffer.readline
import copy

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

    dp = [0]*(S+1)
    dp[0] = 1
    for num in a:
        dp2 = dp.copy()
        for i in range(S-num+1):
            dp2[num+i] += dp[i]
        for i in range(S+1):
            dp[i] += dp2[i]
            dp[i] %= MOD
    
    print(dp[-1]%MOD)

if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

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


fac_inv2 = pow(2,MOD-2,MOD)

dp = np.zeros(s,"int64")

for i in range(n):
    
    newdp = dp.copy()
    if a[i]<s:
        newdp[a[i]:] += dp[:s-a[i]] * fac_inv2 % MOD
    if a[i]<=s:
        newdp[a[i]-1] += 1
    dp = newdp % MOD

ans = dp[-1]
ans *= pow(2,n-1,MOD)
ans %= MOD
print(ans)

Solution (Python):
import sys
import math

sys.setrecursionlimit(10**7)

n, s = map(int, input().split())
a = list(map(int, input().split()))
dp = [0 for _ in range(s+1)]
dp[0] = 1
for i in range(n):
    _dp = [0 for _ in range(s+1)]
    for j in range(s+1):
        if j+a[i] <= s:
            _dp[j+a[i]] += dp[j]
            _dp[j+a[i]] %= 998244353
        _dp[j] += 2*dp[j]
        _dp[j] %= 998244353
    dp = _dp
print(dp[s])

Solution (Python):

mod = 998244353

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

dp = []
for i in range(N+1):
    
    dp.append([0]*(S+1))


dp[0][0] = 1



for i in range(N):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= mod
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= mod        
        if(j >= A[i]):
            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()))
p=998244353

data=[[0]*(s+1) for i in range(n)]

gen=data[0]
gen[0]=2
if(a[0]<=s):
    gen[a[0]]+=1

for i in range(1,n):
    gen=data[i]
    mae=data[i-1]
    for j in range(s+1):
        gen[j]=mae[j]*2
        if(j-a[i]>=0 and j-a[i]<=s):
            gen[j]+=mae[j-a[i]]
        gen[j]%=p

print(data[-1][-1])

Solution (Python):
N,S=map(int,input().split())
A=list(map(int,input().split()))
pr=998244353
def gya(n):
    return pow(n,pr-2,pr)
p=pow(2,N-1,pr)
l=[0]*(S+1)
g=gya(2)
for i in A:
    for j in range(S-i,-1,-1):
        l[i+j]=(l[i+j]+(l[j]*g))%pr
    if i<=S:
        l[i]+=p
print(l[-1])

Solution (Python):
import sys
input = sys.stdin.buffer.readline

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


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

for i in range(n):
    if i == 0:
        dp[0][0] = 2
        if a[i] < s+1:
            dp[0][a[i]] = 1
        continue

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

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

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

*A, = map(int, input().split())

mod = 998244353

sumT = [0]*6005
sumT[0] = 1
sumT[A[0]] = 1

for a in A[1:]:
    for j in range(3001):
        sumT[j] *= 2

    for j in range(3000, -1, -1):
        sumT[j+a] += sumT[j] // 2
        sumT[j+a] %= mod
        sumT[j] %= mod

    sumT[0] += 1
    sumT[0] %= mod

    sumT[a] += 1
    sumT[a] %= mod


print(sumT[S] % mod)

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

mod = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
dp = [0] * (S+1)
dp[0] = pow(2, N, mod)
two_inv = pow(2, mod-2, mod)
for i, a in enumerate(A):
    for j in range(a, S+1)[::-1]:
        dp[j] = (dp[j] + dp[j-a] * two_inv) % mod
print(dp[S])

Solution (Python):
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
L = [[0 for i in range(S+1)] for j in range(N+1)]
L[0][0] = 1
for j, a in enumerate(A):
  for i in range(S+1):
    if i < a:
      L[j+1][i] = (2 * L[j][i]) % mod
    else:
      L[j+1][i] = (2 * L[j][i] + L[j][i-a]) % mod
print(L[N][S])

Solution (Python):
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 998244353; INF = float("inf")

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


def main():
	N, S = getlist()
	A = getlist()
	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] %= con
			w = A[i]
			if j + w <= S:
				DP[i + 1][j + w] += DP[i][j]
				DP[i + 1][j + w] %= con

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


if __name__ == '__main__':
	main()

Solution (Python):
import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, s = map(int, input().split())
    dp = [0] * (s + 1)
    dp[0] = 1
    res = 0
    A = list(map(int, input().split()))
    for a in A:
        ndp = [2 * t % MOD for t in dp]
        if s >= a:
            for i in range(s - a, -1, -1):
                ndp[i + a] += dp[i]
                ndp[i + a] %= MOD
        dp = ndp


    print(dp[s] % MOD)
resolve()

Solution (Python):
from collections import defaultdict

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

dp = [0]*(S+1)
dp[0] = 1
for a in A:
    ndp = [0]*(S+1)
    for total,cnt in enumerate(dp):
        ndp[total] += dp[total]*2
        ndp[total] %= MOD
        if total+a <= S:
            ndp[total+a] += dp[total]
            ndp[total+a] %= MOD
    dp = ndp

print(dp[-1]%MOD)

Solution (Python):


import sys
sys.setrecursionlimit(300000)

MOD = 998244353  
INV = pow(2, MOD - 2, MOD)

def calc_fraction_mod(numerator):
    '''
        returns numerator / denominator (mod MOD)
    '''
    
    return numerator * INV % MOD


def solve(N: int, S: int, A: "List[int]"):
    A.sort()
    dp = [0] * (S + 1)
    dp[0] = pow(2, N, MOD)
    for i, a in enumerate(A):
        for s in range(S + 1)[::-1]:
            if dp[s] == 0:
                continue
            if s + a <= S:
                dp[s + a] += calc_fraction_mod(dp[s])
                dp[s + a] %= MOD
    print(dp[S])

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    S = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, S, A)

if __name__ == '__main__':
    main()

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

dp = [[0 for i in range(s+1)] for j in range(n+1)]
mod = 998244353

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



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

Solution (Python):
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n,s=NM()
l=[0]+L()
dp=[[0]*(s+1) for i in range(n+1)]
dp[0][0]=1
ans=0
mod=998244353
inv2=pow(2,mod-2,mod)
pow2n=pow(2,n,mod)
for i in range(1,n+1):
    x=l[i]
    for j in range(s+1):
        dp[i][j]=dp[i-1][j]
    for j in range(x,s+1):
        dp[i][j]+=dp[i-1][j-x]*inv2
        dp[i][j]%=mod
ans=dp[-1][-1]*pow(2,n,mod)%mod
print(ans)

Solution (Python):
def inv_mod(a, p=10**9+7):
    p = abs(p)
    a %= p
    stack = []
    p0 = p
    while a > 1:
        d, a, p = p//a, p%a, a
        stack.append(d)
    x, y = 1, 0
    while stack:
        d = stack.pop()
        x, y = y-d*x, x
    return x % p0

MOD = 998244353
inpl = lambda: list(map(int,input().split()))
N, S = inpl()
A = inpl()
F = [[0]*(S+1) for _ in range(N+1)]
F[0][0] = pow(2,N,MOD)
p = inv_mod(2,MOD)

for k in range(1,N+1):
    for s in range(S+1):
        if F[k-1][s] > 0:
            F[k][s] += F[k-1][s]
            F[k][s] %= MOD
            t = s + A[k-1]
            if t <= S:
                F[k][t] += F[k-1][s] * p
                F[k][t] %= MOD
print(F[N][S])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul
from decimal import Decimal

mod = 998244353
INF = 10 ** 13
sys.setrecursionlimit(2147483647)
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


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


print(dp[s])

Solution (Python):
N,S=map(int,input().split())
A=list(map(int,input().split()))
dp=[[0 for i in range(3001)] for j in range(3001)]

dp[0][0]=1

mod=998244353

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

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

Solution (Python):




































N,S=map(int,input().split())
A=[int(i) for i in input().split()]
mod=998244353
dp=[[0 for j in range(S+1)]for i in range(N+1)]
pow2N=pow(2,N,mod)
dp[0][0]=pow2N
inv2=pow(2,mod-2,mod)
for i in range(N):
    for j in range(S+1):
        if dp[i][j]!=0:
            dp[i+1][j]+=dp[i][j]
            dp[i+1][j]%=mod
            if j+A[i]<=S:
                dp[i+1][j+A[i]]+=(inv2*dp[i][j])%mod
                dp[i+1][j+A[i]]%=mod
print(dp[N][S])

Solution (Python):
N,S=map(int,input().split())
A = list(map(int,input().split()))
mod=998244353
ans=[[0 for e in range(S+1)] for f in range(N+1)]
ans[0][0]=1
for i in range(N):
 for k in range(S+1):
  ans[i+1][k]=ans[i][k]*2
  ans[i+1][k]%=mod
 for j in range(A[i],S+1):
  ans[i+1][j]+=ans[i][j-A[i]]
  ans[i+1][j]%=mod
print(ans[N][S])

Solution (Python):
def main():
    mod=998244353
    n,s=map(int,input().split())
    A=list(map(int,input().split()))
    DP=[[0]*(s+1) for _ in range(n+1)]
    p=1
    for i in range(n+1):
        DP[i][0]=p
        p*=2
        p%=mod
    for i,a in enumerate(A):
        for j in range(1,s+1):
            DP[i+1][j]=DP[i][j]*2
            if j>=a:
                DP[i+1][j]+=DP[i][j-a]
            DP[i+1][j]%=mod
    print(DP[-1][-1])
    
    
if __name__=='__main__':
    main()

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

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

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

beki2 = [1]
MOD = 998244353
for i in range(4000):
    beki2.append(beki2[-1]*2%MOD)

for i in range(n):
    ai = a[i]
    if(ai<=s):
        dp[i+1][ai] += beki2[i]
    for j in range(s+1):
        valj = dp[i][j]
        dp[i+1][j] += (valj * 2)
        wa = j + ai
        if(wa <= s):
            dp[i+1][wa] += valj
    for j in range(s+1):
        dp[i+1][j] %= MOD

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

Solution (Python):

import sys

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

answer = [0 for _ in range(S+1)]
power2 = 1

for a in A:
  answer_next = [(2*b)%mod for b in answer]
  if a<=S:
    answer_next[a] = (answer_next[a]+power2)%mod
    for i in range(a+1,S+1):
      answer_next[i] = (answer_next[i]+answer[i-a])%mod
  answer = answer_next
  power2 = (2*power2)%mod

print(answer[S])

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

al = list(map(int,input().split()))

ans = 0
dp = [0 for _ in range(s + 1)]
dp[0] = 1
for i in range(n):
    for k in range(s, -1, -1):
        if k - al[i] < 0:
            dp[k] = 2 * dp[k]
        else:
            dp[k] = 2 * dp[k] + dp[k-al[i]]
        dp[k] %= 998244353

print(dp[-1])

Solution (Python):
import sys
input = sys.stdin.buffer.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(N):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j]*2
        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[-1][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)]
dp[0][0]=2
if a[0]<=s: dp[0][a[0]]=1

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

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

div = pow(2, MOD-2, MOD)

DP = [0] * (S+1)
DP[0] = pow(2, N, MOD)
for a in A:
	for i in range(S-a, -1, -1):
		if DP[i] == 0: continue
		DP[i+a] = (DP[i+a] + DP[i] * div) % MOD

print(DP[S])

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

Solution (Python):

mod = 998244353

def modinv(x, m = mod):
    b = m
    u = 1
    v = 0
    while b:
        t = x // b
        x -= t * b
        x, b = b, x
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u

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

    pow2 = [0 for _ in range(n+1)]
    pow2[0] = 1
    for i in range(n):
        pow2[i+1] = (pow2[i] * 2) % mod

    ans = 0
    dp = [0 for _ in range(s+1)]
    dp[0] = pow2[n]
    for i in range(n):
        dp_next = [0 for _ in range(s+1)]
        for j in range(s+1):
            dp_next[j] = (dp_next[j] + dp[j]) % mod
            if j + a[i] <= s:
                dp_next[j+a[i]] = (dp_next[j+a[i]] + (dp[j] * modinv(2))) % mod
        dp = dp_next

    print(dp[s])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *

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
MOD = 998244353

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()))
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])

Solution (Python):
import numpy as np

MOD = 998244353

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

dp = np.zeros((N+1, S+1), np.int64)
dp[0][0] = 1
for n, A in enumerate(As):
    dp[n+1, :] = dp[n, :] * 2
    dp[n+1, A:] += dp[n, :-A]
    dp[n+1] %= 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)]
dp[0][0] = 1
for i in range(N):
    dp.append([d * 2 % MOD for d in dp[-1]])
    for k in range(A[i], S + 1):
        dp[-1][k] += dp[-2][k - A[i]]

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

Solution (Python):
from collections import defaultdict
MOD = 998244353
n, s = map(int, input().split())
a = list(map(int, input().split()))

two_inv = pow(2, MOD - 2, MOD)


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


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 _ in range(n+1)]
dp[0][0] = 1

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

Solution (Python):
from collections import defaultdict

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

dp = [0]*(S+1)
dp[0] = 1
for a in A:
    ndp = [0]*(S+1)
    for total,cnt in enumerate(dp):
        ndp[total] += (dp[total]*2)%MOD
        if total+a <= S:
            ndp[total+a] += dp[total]
            ndp[total+a] %= MOD
    dp = ndp

print(dp[-1]%MOD)

Solution (Python):
import os

import itertools
import sys



if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353

N, S = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))


def test(N, S, A):
    A = np.array(A)
    ret = 0
    for choices in itertools.product([True, False], repeat=N):
        choices = np.array(choices, dtype=bool)
        if A[choices].sum() == S:
            ret += 2 ** (N - choices.sum())
    print(ret)














div2 = pow(2, MOD - 2, MOD)

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

Solution (Python):
import numpy as np
import numba
@numba.njit("void(i8,i8,i8[:])", cache=True)
def solve(N,S,A):
    dp = np.zeros((N+1, S+1), dtype=np.int64)
    dp[0][0] = 1
    mod = 998244353
    for i, a in enumerate(A, 1):
        for s in range(S+1):
            if s-a >= 0:
                dp[i][s] = (dp[i-1][s] * 2 + dp[i-1][s-a]) % mod
            else:
                dp[i][s] = dp[i-1][s] * 2 % mod
    print(dp[N][S])

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

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 998244353
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from copy import copy

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

    
    dp = [[0] * (s + 1) for _ in range(n)]
    dp[0][0] = 2
    if a[0] <= s:
        dp[0][a[0]] = 1

    for i, x in enumerate(a[1:], 1):
        dp[i] = [y * 2 % MOD for y in dp[i - 1]]
        for j in range(s + 1):
            cur = j + x
            if cur > s:
                break
            dp[i][cur] += dp[i - 1][j]

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


if __name__ == '__main__':
    main()

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

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

dp = dpinit((N+1,S+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
        dp[i+1][j] %= MOD
        if j+a <= S:
            dp[i+1][j+a] += dp[i][j]
            dp[i+1][j+a] %= MOD
        
print(dp[N][S]%MOD)

Solution (Python):
K = 96
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
P = 998244353
pa = (1 << 64) - ((1 << 64) % P)
m = int(("1" * 32 + "0" * 64) * 3030, 2)
modP = lambda x: x - ((x & m) >> 64) * pa
s = 1 << K * S
for a in A:
    s = 2 * s + (s >> K * a)
    s = modP(s)
print((s & ((1 << K) - 1)) % P)

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):
    dp[i+1][0] = pow(2,i+1,mod)
    for j in range(1,S+1):
        dp[i+1][j] += 2*dp[i][j]
        if j>=A[i]:
            dp[i+1][j] += dp[i][j-A[i]]
        dp[i+1][j] %= mod
ans = dp[-1][S]
print(ans)