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

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 998244353

def solve():
    n,s = LI()
    a = LI()
    dp = [0]*(s+1)
    dp[0] = pow(2,n,mod)
    inv = pow(2,mod-2,mod)
    for i in a:
        for k in range(s)[::-1]:
            nk = k+i
            if nk > s:
                continue
            dp[nk] += dp[k]*inv%mod
            dp[nk] %= mod
    print(dp[s])
    return


if __name__ == "__main__":
    solve()

Solution (Python):
Q = 998244353
def main():
    N, S = map( int, input().split())
    A = list( map( int, input().split()))
    invtwo = pow(2, Q-2, Q)
    
    
    dp = [pow(2, N, Q)]+[0]*S
    for i in range(N):
        a = A[i]
        for i in range(S, a-1,-1):
            
            if dp[i-a] > 0:
                dp[i] += dp[i-a]*invtwo%Q
                dp[i] %= Q
        
    print(dp[S])
                
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):
import sys
input = sys.stdin.readline
N, S = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353

dp = [0] * (S + 1)
dp[0] = 1
md = pow(2, mod - 2, mod)
for i in range(N):
  for x in range(S, -1, -1):
    if dp[x] == 0: continue
    if x + a[i] <= S:
      dp[x + a[i]] += dp[x] * md % mod
      dp[x + a[i]] %= mod
print(dp[-1] * pow(2, N, mod) % mod)

Solution (Python):
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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):
  for si in range(s+1):
    dp[i+1][si] += dp[i][si]*2
    dp[i+1][si] %= mod
    if not 0 <= si+A[i] < s+1:continue
    dp[i+1][si+A[i]] += dp[i][si]
    dp[i+1][si+A[i]] %= mod

print(dp[n][s])

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

half = 499122177

for i in range(N):

    for j in range(S,-1,-1):

        if j + A[i] <= S:
            dp[j+A[i]] += dp[j] * half
            dp[j+A[i]] %= mod

print (dp[-1] % mod)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

M =998244353

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

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

Solution (Python):
import sys
import numpy as np

n, s, *aaa = map(int, sys.stdin.buffer.read().split())
MOD = 998244353

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

for a in aaa:
    ndp = dp * 2 % MOD
    if a <= s:
        ndp[a:] += dp[:-a]
    dp = ndp % MOD

print(dp[s])

Solution (Python):
mod=998244353

n,s=map(int,input().split())
A=list(map(int,input().split()))
div2=pow(2,mod-2,mod)
dp=[0]*(s+1)
dp[0]=pow(2,n,mod)

for a in A:
    newdp=[0]*(s+1)
    for i in range(s,a-1,-1):
        before=i-a
        newdp[i]+=dp[before]*div2%mod
        newdp[i]%=mod
    for i in range(s+1):
        newdp[i]+=dp[i]
        newdp[i]%=mod
    dp=newdp
print(dp[-1])

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

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

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:
    newDp = [d * 2 % MOD for d in dp]

    for s in range(S + 1):
        if s + a <= S:
            newDp[s + a] += dp[s]

    dp = newDp

print(dp[S] % MOD)

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

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 sys
input = sys.stdin.readline

mod = 998244353

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

inv2 = pow(2, mod-2, mod)
dp = [[0]*(S+1) for _ in range(N+1)]

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

print(dp[N][S])

Solution (Python):
n,s = map(int,input().split())
a = list(map(int,input().split()))
mod = 998244353
half = mod//2+1
now = [0 for _ in range(s+1)]
dp00 = 1
for _ in range(n):
  dp00 *= 2
  dp00 %= mod
now[0] = dp00
for i in range(n):
  for j in range(s+1)[::-1]:
    if j + a[i] <= s:
      now[j+a[i]] += now[j] * half
      now[j+a[i]] %= mod
print(now[-1]%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()))


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

Solution (Python):
MOD = 998244353
class mint:
    def __init__(self, i):
        self.i = i
    def __add__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __radd__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __mul__(self, m):
        return mint(self.i * (m.i if isinstance(m, mint) else m) % MOD)
    def __sub__(self, m):
        t = self.i - (m.i if isinstance(m, mint) else (m % MOD))
        if t < 0:
            t += MOD
        return mint(t)
    def __pow__(self, m):
        i = self.i
        return mint(pow(i, m, MOD))
    def __truediv__(self, m):
        return mint(self.i * pow(m, MOD - 2, MOD) % MOD)
    def __repr__(self):
        return repr(self.i)


n, s = map(int, input().split())
dp = [mint(0)] * (s + 1)
dp[0] = mint(2) ** n
i2 = mint(2) ** (MOD-2)
for a in map(int, input().split()):
    for i in range(s, -1, -1):
        if a + i <= s:
            dp[a + i] += dp[i] * i2
print(dp[s])

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


main()

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

Solution (Python):
mod = 998244353
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

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

    half = pow(2, mod-2, mod)
    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+1][j] + dp[i][j])%mod
            if j+a <= S:
                dp[i+1][j+a] = (dp[i+1][j+a] + (dp[i][j] * half)%mod)%mod
    print((dp[-1][S] * pow(2, N, mod))%mod)


if __name__ == '__main__':
    main()

Solution (Python):
MOD = 998244353

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

dp = [0] * (s+2)

dp[0] = 1

for a in As:
    for i in range(s+1, -1, -1):
        if i - a < 0:continue
        dp[i] += dp[i-a] * (MOD+1) // 2
        dp[i] %= MOD

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

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

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

poly=[0 for i in range(3001)]
poly[0]=1
for i in range(N):
    for j in range(3000,-1,-1):
        if j>=A[i]:
            poly[j]=inv*poly[j-A[i]]+poly[j]
            poly[j]%=mod

res=pow(2,N,mod)*poly[S]
res%=mod
print(res)

Solution (Python):
MOD = 998244353
n, s = map(int, input().split())
a = list(map(int, input().split()))
f = [0] * (s + 1)
f[0] = pow(2, n, MOD)
v = pow(2, MOD - 2, MOD)
for x in a:
    for j in range(s, x - 1, -1):
        f[j] += f[j - x] * v
    for j in range(s + 1):
        f[j] %= MOD
print(f[s])

Solution (Python):


import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,s,*a = map(int,read().split())

MOD = 998244353
def mul(c,m,dp): 
    for i in range(m,c-1,-1):
        dp[i] *= 2
        dp[i] += dp[i-c]
        dp[i] %= MOD
    for i in range(min(m,c-1),-1,-1):
        dp[i] *= 2
        dp[i] %= MOD

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

for i in a:
    mul(i,s,dp)

print(dp[-1]%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):


import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():
    n,m=map(int,input().split())
    a = [int(x) for x in input().split()]
    mod=998244353
    hf=(mod+1)//2
    dp=[0]*(m+1)
    dp[0]=(1<<n)%mod
    for x in a:
        for i in reversed(range(m+1-x)):
            dp[i+x]+=dp[i]*hf
            dp[i+x]%=mod
    print(dp[m])


BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
    main()

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

Solution (Python):
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n, s = na()
a = na()

def invl(a, mod):
    b = mod
    p = 1; q = 0
    while b > 0:
        c = a // b
        a, b = b, a%b
        p, q = q, p-c*q
    return p + mod if p < 0 else p

mod = 998244353
i2 = invl(2, mod)
dp = [0] * (s+1)
dp[0] = pow(2, n, mod)

for x in a:
    for i in range(s, x-1, -1):
        dp[i] += dp[i-x] * i2
        dp[i] %= mod

print(dp[s] % mod)

Solution (Python):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998244353

N, S, *A = map(int, read().split())

U = 3010

f = np.zeros(U+1, np.int64)
f[0] = 1
for a in A:
    ff = 2 * f
    ff[a:] += f[:-a]
    ff %= MOD
    f = ff

print(f[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])