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



Sample input:
3 4
2 2 4


Sample output:
6

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

Submission status: Accepted

Solution code:
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)]

# dp[i][j] = {A_1,…,A_i}の部分集合の部分集合で、和がjとなるものの個数

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

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

#H[x][y]:1,...xに制限したときに,和がyになるのは何個?
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])

Submission status: Accepted

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

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

#H[x][y]:1,...xに制限したときに,和がyになるのは何個?
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])

Submission status: Accepted

Solution code:
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.copy()
    dp2=dp[:-ai].copy()
    dp*=2
    dp[ai:]+=dp2#[:-ai]
    #ans+=dp[s]*pow(2,n-cnt,mod)
    #dp=dp2
    #ans%=mod
    dp%=mod
print(dp[s])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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): # a^-x (0 <= x <= 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): # 0 <= x <= 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])

Submission status: Accepted

Solution code:
import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)
print(dp[N][S])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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")

#solve
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


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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
#print(A)
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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])

Submission status: Accepted

Solution code:
import numpy as np

def main():
    MOD = 998244353
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    
    # dp = [[0] * (S + 1) for i in range(N + 1)]
    # dp[0][0] = 1
    
    dp = np.zeros(S + 1, np.int64)
    dp[0] = 1
    
    for i, a in enumerate(A, start=1):
        # i - 1 番目までの数で 合計が X になる組み合わせが
        # dp[i-1][X] 個あるのであれば、
        # そのdp[i-1][X] 個 のそれぞれに対してAi を加える/加えないの
        # 2パターンが考えられるので、dp[i-1]を2倍する
        dp_next = 2 * dp
        
        # さらに、i - 1 番目までの数で 合計が X - Ai になる組み合わせが
        # dp[i-1][X - Ai] 個ある場合、
        # i番目の数(Ai)を足すことで合計をXにできる
        dp_next[a:] += dp[:-a] # dp[:-a] = dp[:len(dp)-a]       

        # 大きくなりすぎないように逐次MODをとる
        dp_next %= MOD
        
        dp = dp_next

    # print(*dp, sep='\n')
    print(dp[S])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 998244353                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    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())


    # def my_update(seq, L):
    #     n = len(seq)
    #     for i in range(n-1):
    #         seq[i+1] += L[i]

    
    # n, s = mi()
    # L = lmi()
    # dp = [[0] * (n + 1) for j in range(s + 1)]    # chain の長さ、場合のかず
    # # print(dp)
    # for i in range(n):
    #     for j in range(s, -1, -1):
    #         if j == 0 and L[i] <= s:
    #             dp[L[i]][1] += 1
    #         elif j + L[i] <= s and dp[j]:
    #             my_update(dp[j + L[i]], dp[j])    # counter
    #     # print(dp)
    
    # ans = 0
    # for chain_len, num in enumerate(dp[s]):
    #     ans = (ans + pow(2, n - chain_len, mod) * num) % mod
    # print(ans)


    # write-up solution
    """
    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):
        # print(power_memo)
        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)
    print(power_memo[s])



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from copy import copy
import numpy as np
N,S=map(int,input().split())
A=list(map(int,input().split()))
dp=np.zeros(S+100,np.int64)
dp[0]=1
for i in range(N):
    buf=copy(dp)
    dp=2*dp
    dp[A[i]:]+=buf[:-A[i]]
    dp%=998244353
print(dp[S]%998244353)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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

mod = 998244353
ans = 0
for i in range(n):
    for j in range(s+1):
        if j+a[i] <= s:
            dp[i+1][j+a[i]] += dp[i][j]

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



print(dp[n][s])

Submission status: Accepted

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

Submission status: Accepted

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

print(dp[n][s])

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
from sys import stdin
input = stdin.readline
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 998244353

def ddprint(x):
  if DBG:
    print(x)

hf = pow(2,R-2,R)
n,s = inm()
a = inl()
dp = [[0]*(s+1) for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = pow(2,n,R)
sm = 0
for i in range(1,n+1):
    dp[i] = [x for x in dp[i-1]]
    for j in range(s):
        if dp[i-1][j]>0 and j+a[i-1]<=s:
            dp[i][j+a[i-1]] = (dp[i][j+a[i-1]]+dp[i-1][j]*hf)%R
    #ddprint(i)
    #ddprint(dp[i])
print(dp[n][s])

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 998244353
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n2 = [1 for _ in range(3010)]
for i in range(1, 3010):
    n2[i] = n2[i - 1] * 2 % mod

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,s = na()
a = na()
mod = 998244353
dp = [0]*(s+1)
dp[0] = 1

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

print(dp[s]%mod)

Submission status: Accepted

Solution code:
MOD = 998244353

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, S = ZZ()
    A = ZZ()
    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 A[i] <= j <= S: dp[i+1][j] += dp[i][j-A[i]]
            dp[i+1][j] %= MOD
    print(dp[N][S])

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 998244353
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n2 = [1 for _ in range(3010)]
for i in range(1, 3010):
    n2[i] = n2[i - 1] * 2 % mod

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

Submission status: Accepted

Solution code:
N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
DP=[0]*(S+1)
DP[0]=pow(2,N,mod)
INV=pow(2,mod-2,mod)
for a in A:
    for i in range(S-a,-1,-1):
        DP[i+a]=(DP[i]*INV+DP[i+a])%mod       
print(DP[S])

Submission status: Accepted

Solution code:
import sys
mod = 998244353

def solve():
    input = sys.stdin.readline
    N, S = map(int, input().split())
    A = [int(a) for a in input().split()]
    DP = [[0 for _ in range(S + 1)] for i in range(N)]
    DP[0][0] = 2
    if A[0] <= S: DP[0][A[0]] = 1
    ans = 0
    for i, a in enumerate(A[1:]):
        for s in range(S + 1):
            if DP[i][s] > 0:
                DP[i+1][s] += (DP[i][s] * 2) % mod
                DP[i+1][s] %= mod
                if s + a <= S:
                    DP[i+1][s+a] += DP[i][s]
                    DP[i+1][s+a] %= mod         
    print(DP[N-1][S])
    #print(DP)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

Submission status: Accepted

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

dp = [0 for _ in range(s+1)]
dp[0] = 1
for v in a:
    for i in reversed(range(s-v+1)):
        dp[i+v] += dp[i] * (MOD+1) // 2
        dp[i+v] %= MOD

print(dp[s] * pow(2, n, MOD) % MOD)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    md=998244353
    n,s=MI()
    aa=LI()
    dp=[0]*(s+1)
    dp[0]=1
    inv=pow(2,md-2,md)
    for k,a in enumerate(aa):
        for i in range(s-a,-1,-1):
            dp[i+a]=(dp[i+a]+dp[i]*inv)%md
        #print(k,dp)
    ans=dp[s]*pow(2,n,md)%md
    print(ans)

main()