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):

MOD = 998244353
class mint:
    def __init__(self, x):
        if isinstance(x, int):
            self.x = x % MOD 
        elif isinstance(x, mint):
            self.x = x.x
        else:
            self.x = int(x) % MOD 
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __floordiv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rfloordiv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )


n,s = map(int, input().split())
a = list(map(int, input().split()))
import copy
dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
dp[0][0]=pow(2,n,MOD)
div=pow(2,MOD-2,MOD)
for i in range(n):
    for j in range(s+1):
        dp[i+1][j]=dp[i][j]
        if j-a[i]>=0:
            dp[i+1][j]+=dp[i][j-a[i]]*div
        dp[i+1][j]%=MOD
print(dp[n][s])

Solution (Python):

MOD = 998244353
class mint:
    def __init__(self, x):
        if isinstance(x, int):
            self.x = x % MOD 
        elif isinstance(x, mint):
            self.x = x.x
        else:
            self.x = int(x) % MOD 
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __floordiv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rfloordiv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )


n,s = map(int, input().split())
a = list(map(int, input().split()))
import copy
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]=dp[i][j]*2
        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):
P = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0]*(S+1) for i in range(N+1)]


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

Solution (Python):
n,s=map(int,input().split())
a=[int(j)for j in input().split()]
dp=[0]*(3000+1)
dp[0]=1
import numpy as np
pre=np.array(dp)
mod=998244353
for i in a:
    dp=pre*2
    dp[i:]+=pre[:-i]
    dp%=mod
    pre=dp
print(dp[s])

Solution (Python):
from collections import defaultdict
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, ai in enumerate(a):
    for j in range(s + 1):
        if j - ai >= 0:
            dp[i + 1][j] = (dp[i][j] * 2 + dp[i][j - ai]) % MOD
        else:
            dp[i + 1][j] = dp[i][j] * 2 % MOD


print(dp[n][s])

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

inv_2 = pow(2, mod-2, mod)
dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
dp[0][0] = pow(2, n, mod)

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

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


print(dp[n][s])

Solution (Python):
import numpy as np
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
dp=np.zeros([n+1,s+1],int)
dp[0][0]=1
for i in range(1,n+1):
  dp[i][:]=dp[i-1][:]*2
  dp[i][a[i-1]:]+=dp[i-1][:-a[i-1]]
  dp[i][:]%=mod
print(dp[n][s])

Solution (Python):
import numpy as np

N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
f = np.zeros(3100, np.int64)

ans = 0
f[0] = 1
for a in A:
    g = f.copy()
    f[a:] += g[:-a]
    f += g
    f %= mod

print(f[S])

Solution (Python):
def f_knapsack_for_all_subsets(MOD=998244353):
    N, S = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]

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

print(f_knapsack_for_all_subsets())

Solution (Python):
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353

gyaku=pow(2,mod-2,mod)
N2=pow(2,N-1,mod)
dp=[0 for n in range(3001)]
for n in range(N):
    a=A[n]
    for s in range(0,S+1)[::-1]:
        if s+a<=S:
            dp[s+a]+=dp[s]*gyaku%mod
            dp[s+a]%=mod
    dp[a]+=N2
    dp[a]%=mod

print(dp[S])

Solution (Python):
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353

gyaku=pow(2,mod-2,mod)
N2=pow(2,N-1,mod)
dp=[[0,0] for n in range(3001)]
for n in range(N):
    a=A[n]
    for s in range(0,S+1)[::-1]:
        if s+a<=S:
            dp[s+a][1]+=dp[s][1]*gyaku%mod
            dp[s+a][1]%=mod
    dp[a][1]+=N2

print(dp[S][1])

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, s, *a = map(int, read().split())
dp = [0] * (s + 1)
dp[0] = 1
mod = 998244353
for aa in a:
    for j in range(s, -1, -1):
        ss = j + aa
        if ss <= s:
            dp[ss] += dp[j]
            dp[ss] %= mod
        dp[j] *= 2
        dp[j] %= mod
print(dp[-1])

Solution (Python):


LI = lambda: list(map(int, input().split()))


N, S = LI()
A = LI()

MOD = 998244353


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


if __name__ == "__main__":
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=998244353
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,S=map(int,input().split())
A=tuple(map(int,input().split()))
dp=[[0]*3001 for _ in range(N+1)]
dp[0][0]=1
for i in range(N):
    for j in range(3001):
        dp[i+1][j]+=dp[i][j]*2
        dp[i+1][j]%=MOD
        if j-A[i]>=0:
            dp[i+1][j]+=dp[i][j-A[i]]
            dp[i+1][j]%=MOD
print(dp[-1][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 in range(N):
  for j in range(S+1):
    if j>=A[i]:
      dp[i+1][j] += dp[i][j-A[i]]
    dp[i+1][j] += 2 * dp[i][j]
    dp[i+1][j] %= MOD
      
print(dp[-1][-1])

Solution (Python):
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")
MOD = 998244353


def main():
    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:
                continue
            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):
import sys
from functools import lru_cache

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    MOD = 998244353
    N, S, *A = map(int, read().split())

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

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

    print(dp[N][S])
    return


if __name__ == '__main__':
    main()

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, s = LI()
a = LI()

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

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, s = LI()
a = LI()

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

Solution (Python):
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def S(): return sys.stdin.readline().rstrip()

N,S = map(int,S().split())
A = [0] + LI()
mod = 998244353

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



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

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

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

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

temp = [1] + [0] * s
for i in range(n):
    temp2 = [0] * (s + 1)
    for j in range(s + 1):
        temp2[j] += temp[j] * 2
        temp2[j] %= mod
    for j in range(s + 1 - a[i]):
        temp2[j + a[i]] += temp[j]
        temp2[j + a[i]] %= mod
    temp = temp2
print(temp[s])

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, s = LI()
a = LI()

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

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

dp = [[0]*(3001) 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] % 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=map(int,input().split())
A=[0]+list(map(int,input().split()))

H=[[0]*(S+1) for i in range(N+1)]


M=998244353

for x in range(N+1):
    H[x][0]=2**x

for x in range(1,N+1):
    for s in range(S+1):
        if s>=A[x]:
            H[x][s]=(2*H[x-1][s]+H[x-1][s-A[x]])%M
        else:
            H[x][s]=(2*H[x-1][s])%M

print(H[-1][-1])

Solution (Python):
N,S=map(int,input().split())
A=[0]+list(map(int,input().split()))

H=[[0]*(S+1) for i in range(N+1)]


M=998244353

for x in range(N+1):
    H[x][0]=1

for x in range(1,N+1):
    for s in range(S+1):
        if s>=A[x]:
            H[x][s]=(2*H[x-1][s]+H[x-1][s-A[x]])%M
        else:
            H[x][s]=(2*H[x-1][s])%M

print(H[-1][-1])

Solution (Python):
import numpy as np
n,s=map(int, input().split( ))
*a,=map(int, input().split( ))
l=min(s+1,3001)
dp=np.zeros(l,dtype = int)
dp[0]=1
mod=998244353
ans=0
cnt=0
for ai in a:
    
    dp2=dp[:-ai].copy()
    dp*=2
    dp[ai:]+=dp2
    
    
    
    dp%=mod
print(dp[s])

Solution (Python):
def main():
    import sys
    mod = 998244353
    def input(): return sys.stdin.readline().rstrip()
    n,s = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [0]*(s+1)
    dp[0] = 1
    import numpy as np
    dp = np.array(dp)
    for i in range(n):
        dp[a[i]:] = (2*dp[a[i]:]%mod + dp[:-a[i]])%mod
        dp[:a[i]] *= 2
        dp[:a[i]] %= mod
    print(dp[-1])


if __name__ == '__main__':
    main()

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


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

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

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

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

print(DP[-1][S])

Solution (Python):
import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

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

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):
from sys import stdin, setrecursionlimit


def main():
    MOD = 998244353
    input = stdin.buffer.readline
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [0] * (s + 1)
    dp[0] = 1

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

        dp = tmp

    print(dp[-1] % MOD)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

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

print(dp[N][S])

Solution (Python):
n,s,*a=map(int,open(0).read().split())
mod=998244353
dp=[[0]*(s+1) for _ in range(n+1)]
dp[0][0]=pow(2,n,mod)
for i in range(n):
  for j in range(s+1):
    dp[i+1][j]+=dp[i][j]
    dp[i+1][j]%=mod
    if j+a[i]<=s:
      dp[i+1][j+a[i]]+=dp[i][j]*(mod+1)//2
      dp[i+1][j+a[i]]%=mod
print(dp[n][s])

Solution (Python):
import numpy as np

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

dp = np.zeros((N + 1, S + 1), dtype=np.int64)
dp[0][0] = 1
for i in range(N):
    dp[i + 1] = dp[i] * 2
    dp[i + 1, A[i]:] += dp[i, :-A[i]]
    dp[i + 1] %= MOD

print(dp[N][S])

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 998244353
inf = float("INF")


def solve():
    n, s = LI()
    a = LI()
    dp = [[0] * (3001) for _ in range(n)]
    dp[0][0] = 1
    dp[0][a[0]] = 1
    ans = 0
    for i in range(1, n):
        for si in range(a[i], 3001):
            dp[i][si] = dp[i - 1][si - a[i]] % mod
        dp[i][0] += 1
        dp[i][a[i]] += 1
        for si in range(3001):
            dp[i][si] = (dp[i][si] + dp[i - 1][si] * 2) % mod
        ans += dp[i][s]
    print(dp[-1][s] % mod)
    return



if __name__ == '__main__':
    solve()

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

Solution (Python):
def main():
    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])

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, np.int64)
dp[0] = 1

for e in a:
    pre = dp.copy()

    dp = 2 * pre
    dp[e:] += pre[:-e]
    dp %= mod

ans = dp[s]
print(ans)

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

for i, e in enumerate(a, 1):
    for j in range(s + 1):
        dp[i][j] += 2 * dp[i-1][j]
        if j - e >= 0:
            dp[i][j] += dp[i-1][j-e]

        dp[i][j] %= mod

ans = dp[n][s]
print(ans)

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

n,s = readints()
a = readints()

mod = 998244353

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


print(dp[n][s])

Solution (Python):

import sys
import numpy as np

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

answer = np.zeros(S+1).astype(np.int64)
answer[0] = 1

for a in A:
  if a<=S:
    answer[a:] = (2*answer[a:]+answer[:-a])%mod
    answer[:a] = (2*answer[:a])%mod
  else:
    answer = (2*answer)%mod

print(answer[S])

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):
N,S=map(int,input().split())
A=list(map(int,input().split()))

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

print(f(N,S,A))

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



N,S = LI()
A = LI()

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

inv2 = pow(2,mod-2,mod)

d = [0]*(S+1)
d[0] = beki[N]

ans = 0
for i in range(N):
    if 0 <= S-A[i] <= S:
        ans += d[S-A[i]]*inv2
        ans %= mod
    diff = [0]*(S+1)
    for k in range(S-A[i]+1):
        diff[k+A[i]] = d[k]*inv2
    for k in range(S+1):
        d[k] += diff[k]
        d[k] %= mod

print(ans)

Solution (Python):

import sys
import numpy as np

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

answer = np.zeros(3002).astype(np.int64)
power2 = 1

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

print(answer[S])

Solution (Python):
import numpy as np

def main():
    MOD = 998244353
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    
    
    
    
    dp = np.zeros(S + 1, np.int64)
    dp[0] = 1
    
    for i, a in enumerate(A, start=1):
        
        
        
        
        dp_next = 2 * dp
        
        
        
        
        dp_next[a:] += dp[:-a] 

        
        dp_next %= MOD
        
        dp = dp_next

    
    print(dp[S])

if __name__ == '__main__':
    main()

Solution (Python):


import sys






























def main():
    mod = 998244353                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    


    
    """
    Ai それぞれ選ぶ or 選ばないと選択して行った時、足して S にできる組み合わせは何パターンできるか？
    -> 
    まさに二項定理の発想
    fi = 1+x^Ai として
    T = {1, 2, 3} に対する答えは [x^S]f1*f2*f3
    T = {1, 2} に対する答えは [x^S]f1*f2 
    のように計算していく
    全パターン f1*f2*f3 + f1*f2 + f1*f3 + f2*f3 + f1 + f2 + f3 の [x^S] の値が答え
    
    ->
    (1+f1)*...*(1+fi)*...*(1+fn) の x^S の係数と一致
    [x^S] Π{i=1...n} (2 + x^Ai)
    を計算せよ、という問である
    """
    n, s = mi()
    A = lmi()
    power_memo = [0] * (s + 1)
    power_memo[0] = 2
    if A[0] <= s:
        power_memo[A[0]] = 1
    for i in range(1, n):
        
        for j in range(s, -1, -1):
            tmp = (power_memo[j] * 2) % mod
            if j - A[i] >= 0 and power_memo[j - A[i]]:
                tmp += power_memo[j - A[i]]
            power_memo[j] = tmp % mod
    
    print(power_memo[s])



if __name__ == "__main__":
    main()