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

Solution (Python):
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())


n,s=sep()
ar=lis()
ar.insert(0,0)
dp=[[0]*(s+2) for _ in range(n+2)]
dp[0][0]=1
N=998244353
for i in range(1,n+1):
    for j in range(0,s+1):
        dp[i][j]=(2*dp[i-1][j])%N
        if j-ar[i]>=0:
            dp[i][j]=(dp[i][j]+dp[i-1][j-ar[i]])%N

print(dp[n][s])

Solution (Python):
import sys
import copy

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, S = in_nn()
    A = in_nl()

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

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

        dp = next_dp

    print(dp[S])


if __name__ == '__main__':
    main()

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

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

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

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

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

Solution (Python):
N,S=map(int,input().split())
*a,=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):
        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

print(dp[N][S])

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

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

"""
X = (1,2,...,N)の部分集合
Y = Xの部分集合

各i(1 ≤ i ≤ N) について、
1. XにもYにも入れる
2. Xには入れるがYには入れない
3. XにもYにも入れない

dp[i][j] = i番目までの選択をして、sum(Y)==jであるような場合の数
"""

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

Solution (Python):
import numpy as np
from numba import njit, i8


@njit(i8(i8, i8, i8[:]), cache=True)
def solve(N, S, A):
    MOD = 998244353
    dp = np.zeros((N + 1, S + 1), dtype=np.int64)
    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
    return dp[-1][-1]


N, S = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)
print(solve(N, S, A))

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


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

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

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  


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

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

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

DIV = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))







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

for i in range(N):
  nextline = [0] * (S + 1)
  for k in range(S, -1, -1):
    
    
    nextline[k] += dp[k] * 2
    nextline[k] %= DIV

    
    if k + A[i] <= S:
      nextline[k + A[i]] += dp[k]
      nextline[k + A[i]] %= DIV
    
  dp = nextline

print(dp[-1])

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

DIV = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))







dp = [[0] * (S + 1) for j in range(2)]
dp[0][0] = 1

for i in range(N):
  nextline = [[0] * (S + 1) for j in range(2)]
  for k in range(S, -1, -1):
    
    nextline[0][k] += dp[0][k]
    nextline[0][k] += dp[1][k]
    nextline[0][k] %= DIV

    
    if k + A[i] <= S:
      nextline[1][k + A[i]] += dp[0][k]
      nextline[1][k + A[i]] += dp[1][k]
      nextline[1][k + A[i]] %= DIV

    
    nextline[1][k] += dp[0][k]
    nextline[1][k] += dp[1][k]
    nextline[1][k] %= DIV
    
  dp = nextline

print((dp[0][-1] + dp[1][-1]) % DIV)

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

DIV = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))







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

for i in range(N):
  for k in range(S + 1):
    
    dp[i + 1][0][k] += dp[i][0][k]
    dp[i + 1][0][k] += dp[i][1][k]
    dp[i + 1][0][k] %= DIV

    
    if k + A[i] <= S:
      dp[i + 1][1][k + A[i]] += dp[i][0][k]
      dp[i + 1][1][k + A[i]] += dp[i][1][k]
      dp[i + 1][1][k + A[i]] %= DIV

    
    dp[i + 1][1][k] += dp[i][0][k]
    dp[i + 1][1][k] += dp[i][1][k]
    dp[i + 1][1][k] %= DIV

print((dp[-1][0][-1] + dp[-1][1][-1]) % DIV)

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









DIV = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))

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

dp[0][0] = 1
for i in range(N):
  val = A[i]
  for j in range(len(dp[i]) - 1, -1, -1):
    if dp[i][j] == 0:
      continue
    dp[i + 1][j] += dp[i][j] * 2 
    dp[i + 1][j] %= DIV
    if j + val <= S:
      dp[i + 1][j + val] += dp[i][j]
      dp[i + 1][j + val] %= DIV
  
print(dp[-1][-1])

Solution (Python):
n, s = map(int, input().split())
a = list(map(int, input().split()))
a.insert(0, 0)
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 a[i] <= j:
            dp[i][j] += dp[i - 1][j - a[i]]
            dp[i][j] %= mod
ans = dp[n][s]
print(ans)

Solution (Python):

import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()


def main():
    n, s = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 998244353
    dp = np.zeros(3001, dtype=np.int64)
    dp[0] = 1
    for AA in A:
        dp = dp*2+np.concatenate([np.zeros(AA, dtype=np.int64), dp[:3001-AA]])
        dp %= mod
    print(dp[s])





if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

MOD = 998244353

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

dp = np.zeros((N, S + 1))
dp[0, 0] = 2
if A[0] < S + 1:
	dp[0, A[0]] = 1

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

Solution (Python):
MOD = 998244353

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

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

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

Solution (Python):
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [-1 for _ in range(S+1)]
visited = [0]
dp[0] = 1
dp = tuple(dp)
for k in range(N):
  a = A[k]
  nextdp = list(dp)
  nextvisit = []
  for item in visited:
    
    if item + a <= S:
      if nextdp[item+a] == -1:
        nextvisit.append(item+a)
        nextdp[item+a] = 0
      nextdp[item+a] += dp[item]
      nextdp[item+a] %= mod
    
    nextdp[item] += dp[item]
    nextdp[item] %= mod
  dp = tuple(nextdp)
  visited.extend(nextvisit)

print(max(dp[-1], 0))

Solution (Python):
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [0 for _ in range(S+1)]
visited = [0]
dp[0] = 1
dp = tuple(dp)
for k in range(N):
  a = A[k]
  nextdp = list(dp)
  nextvisit = []
  for item in visited:
    
    if item + a <= S:
      if nextdp[item+a] == 0:
        nextvisit.append(item+a)
      nextdp[item+a] += dp[item]
      nextdp[item+a] %= mod
    
    if item <= S:
      nextdp[item] += dp[item]
      nextdp[item] %= mod
  dp = tuple(nextdp)
  visited.extend(nextvisit)

print(dp[-1])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 998244353


def resolve():
    """ 愚直解 """
    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 prev in range(i):
            for j in range(s + 1):
                dp[i][j] += dp[prev][j]
                if a + j > s:
                    continue
                dp[i][a + j] += dp[prev][j]
                dp[i][a + j] %= mod
    print(dp)
    res = 0
    for i in range(1, n + 1):
        res += dp[i][-1]
        res %= mod
    print(res)


def resolve2():
    """ DP + 累積和 """
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    cnt_num = [0] * (s + 1)
    cnt_num[0] = 1
    res = 0
    for i in range(1, n + 1):
        a = A[i - 1]
        for j in range(s + 1):
            dp[i][j] += cnt_num[j]
            dp[i][j] %= mod
            if a + j > s:
                continue
            dp[i][a + j] += cnt_num[j]
            dp[i][a + j] %= mod
        for k in range(s + 1):
            cnt_num[k] = cnt_num[k] + dp[i][k]
            cnt_num[k] %= mod
        res += dp[i][-1]
        res %= mod
    print(res)


if __name__ == '__main__':
    n, s = map(int, input().split())
    A = list(map(int, input().split()))
    resolve2()

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 getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7













''' ABC104 D - We Love ABC
S = '????C?????B??????A???????'
N = len(S)

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

for i in range(N):
    
    for j in range(4):
        if S[i] != '?':
            dp[i + 1][j] += dp[i][j]
            dp[i + 1][j] %= mod
        else:
            dp[i + 1][j] += 3 * dp[i][j]
            dp[i + 1][j] %= mod
    
    if S[i] == 'A' or S[i] == '?':
        dp[i + 1][1] += dp[i][0]
        dp[i + 1][1] %= mod
    if S[i] == 'B' or S[i] == '?':
        dp[i + 1][2] += dp[i][1]
        dp[i + 1][2] %= mod
    if S[i] == 'C' or S[i] == '?':
        dp[i + 1][3] += dp[i][2]
        dp[i + 1][3] %= mod
print(dp[N][3] % mod)
'''


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

Solution (Python):
import numpy as np
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20

class Polynomial:
    def __init__(self,dim=0,const=1):
        self.values = [(dim,const)]
    def __add__(self,other):
        return self.values + other.values


class PolySolver:
    def __init__(self,size):
        self.size = size
        self.f = np.zeros(size, np.int64)
        self.f[0] = 1


    def multiple(self,polynomial,MOD): 
        new_F = np.zeros(self.size, np.int64)
        for dim,const in polynomial:
            if dim != 0:
                g = np.zeros(self.size, np.int64)
                g[dim:] += self.f[:-dim]
            else:
                g = const * self.f.copy()
            new_F += g

        self.f = new_F
        self.f %= MOD

    
    def get_coefficient(self,dim):
        return self.f[dim]
    
def main():
    N,S=mi()
    A=list(mi())
    MOD = 998244353

    poly = PolySolver(3010)
    for a in A:
        f = Polynomial(const=2) + Polynomial(dim=a)
        poly.multiple(f,MOD)

    print(poly.get_coefficient(S))



if __name__ == "__main__":
    main()

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


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

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics

mod = 998244353

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

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

Solution (Python):
mod1,mod2=10**9+7,998244353
mod=mod2
n,s=map(int,input().split())
dp=[0]*(s+1)
dp[0]=1
for a in map(int,input().split()):
    dp=[(2*dp[i]+(0 if i<a else dp[i-a]))%mod for i in range(s+1)]
print(dp[-1])

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

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

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

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

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N, S = getNM()
A = getList()
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] += 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[N][S] % MOD)

Solution (Python):
import numpy as np

MOD = 998244353

def main():
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    dp = np.zeros((n+1, s+1), dtype=np.int64)
    dp[0][0] = 1
    for i, v in enumerate(a):
        dp[i+1] += dp[i]*2
        if v <= s:
            dp[i+1][v:] += dp[i][:-v]
        dp[i+1] %= MOD
    print(int(dp[n][s])%MOD)

if __name__ == "__main__":
    main()

Solution (Python):









import sys
readline = sys.stdin.readline

N,S = map(int, readline().split())
A = list(map(int,readline().split()))
DIV = 998244353


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

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

dp = [[0]*(K+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    x = X[i]
    for j in range(K+1):
        dp[i+1][j] = 2*dp[i][j]
        if j-x>=0:
            dp[i+1][j] += dp[i][j-x]
        dp[i+1][j] %= MOD
print(dp[-1][-1])

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 = map(int, readline().split())
A = list(map(int,readline().split()))

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

Solution (Python):









import sys
readline = sys.stdin.readline

N,S = map(int, readline().split())
A = list(map(int,readline().split()))
DIV = 998244353

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

print(dp[S])

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

Solution (Python):
def main():
    MOD = 998244353
    N, S = list(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, a in enumerate(A):
        n = i + 1
        for s in range(S + 1):
            dp[n][s] += 2 * dp[n - 1][s]
            if s - a >= 0:
                dp[n][s] += dp[n - 1][s - a]
            dp[n][s] %= MOD
    print(dp[N][S])


if __name__ == '__main__':
    main()

Solution (Python):
N,S=map(int,input().split())
A=list(map(int,input().split()))
import numpy as np
d=np.zeros((N+1,S+1),dtype=np.int64)
d[0,0]=1
m=998244353
for i in range(N):
    d[i+1]=d[i]*2%m
    d[i+1,A[i]:]=(d[i+1,A[i]:]+d[i,:-A[i]])%m
print(d[-1,-1])

Solution (Python):
import sys



from collections import deque




def input():
    return sys.stdin.readline().rstrip()


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



if __name__ == "__main__":
    main()

Solution (Python):


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


A_list = [None] + list(map(int, input().rstrip().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_list[i+1]) >=0:
            dp[i+1][j] = dp[i][j - A_list[i+1]]
        
        dp[i+1][j] += 2*dp[i][j]
        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 _ 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):
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 main():
    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+1):
        ai = a[i-1]
        for j in range(s+1):
            dp[i][j] += dp[i-1][j]*2
            if j >= ai:
                dp[i][j] += dp[i-1][j-ai]
            dp[i][j] %= mod
    print(dp[n][s])
            

if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
N, S = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
mod = 998244353
coef = np.zeros(3001, dtype=int)
coef[0] = 1
for a in A:
    coef2 = coef[:-a].copy()
    coef *= 2
    coef[a:] += coef2
    coef %= mod
print(coef[S])

Solution (Python):
import numpy as np
N, S = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
dp = np.array([0] * (3001), dtype=int)
dp[0] = 2
dp[A[0]] = 1
mod = 998244353
for a in A[1:]:
    dpn = np.zeros(3001, dtype=int)
    dpn[a:] = dp[:-a]
    dpn += dp * 2
    dpn %= mod
    dp = dpn
print(dp[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):
        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()))
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):
        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
N, S = map(int, input().split())
A = np.array(list(map(int, input().split())))
P = 998244353
table = np.zeros((N, S+1), dtype=int)
table[0, 0] = 2
if A[0] <= S:
  table[0, A[0]] = 1
for i in range(1, N):
  Ai = A[i]
  table[i] += 2*table[i-1]
  if Ai <= S:
    table[i][Ai:] += table[i-1][:S-Ai+1]
  table[i] = table[i]%P
print(table[N-1][S])

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

if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

N, S = map(int, input().split())
A = np.array(list(map(int, input().split())))
P = 998244353
table = np.zeros((N, S+1), dtype=int)
table[0, 0] = 2
if A[0] <= S:
    table[0, A[0]] = 1
for i in range(1, N):
    Ai = A[i]
    table[i] += 2*table[i-1]
    if Ai <= S:
        table[i][Ai:] += table[i-1][:S-Ai+1]
    table[i] = table[i]%P

print(table[N-1][S])

Solution (Python):
import sys
import bisect
import math
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from operator import itemgetter

n,s=map(int,readline().split())
a=list(map(int,readline().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 sys
input = sys.stdin.readline

M, MOD = 3005, 998244353

dp = [[0 for i in range(M)] for j in range(M)]
n, s = map(int, input().split())
a = list(map(int, input().split()))
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 s >= j + a[i]:
            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()))

MOD = 998_244_353

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

MOD = 998244353

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

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

print(dp[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):
    ai = A[i]
    for j in range(S + 1):
        here = dp[i][j]
        
        dp[i + 1][j] += here
        
        dp[i + 1][j] += here

        dp[i + 1][j] %= MOD

        
        if j + ai <= S:
            dp[i + 1][j + ai] += dp[i][j]
            dp[i + 1][j + ai] %= MOD

print(dp[N][S])