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

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

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 998244353

N, K = MAP()
A = LIST()

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# F

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
from itertools import accumulate, combinations
input = sys.stdin.readline

mod = 998244353

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

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

MOD = 998244353
n, s = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
dp = np.zeros(s+1, dtype=np.int64)
dp[0] = 1
for a in A:
  t = dp.copy() * 2
  t[a:] += dp[:-a]
  t %= MOD
  dp = t
ans = dp[s]
print(ans)

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

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

Submission status: Accepted

Solution code:
MOD=998244353
n,s=map(int,input().split())
a=list(map(int,input().split()))
al=sum(a)
dp=[[0]*3001 for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    for j in range(3001):
        if j==0:
            dp[i+1][j]=pow(2,i+1,MOD)
            continue
        dp[i+1][j]=(dp[i+1][j]+(dp[i][j]*2%MOD))%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:
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])

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, dtype=int)
dp[0] = 1

for i in A:
    ep = dp * 2
    ep[i:] += dp[:-i]
    dp = ep % MOD

print(dp[S])

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, dtype=int)
dp[0] = 1

for i in A:
    ep = dp.copy()
    ep += dp
    ep[i:] += dp[:-i]
    dp = ep % MOD

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

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

    # https://qiita.com/drken/items/dc53c683d6de8aeacf5a#%E9%A1%9E%E9%A1%8C-3
    
    INF = 10**10  # INF+INFを計算してもオーバーフローしない範囲で大きく
    MOD=998244353
    
    I, J =N,S
    # dpテーブル dp[i][j]:=i番目以下で選ばれしa_kの和がjになる通り数
    dp = [[0]*(J+1) for _ in range(I+1)]
    # 初期条件
    dp[0][0] = 1
    # ループ
    for i in range(I):
        for j in range(J+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[I][J])
    
    
    
resolve()

Submission status: Accepted

Solution code:
def main():
    N, S = map(int, input().split())
    A = tuple(map(int, input().split()))

    MOD = 998244353

    dp = [[0]*(S+1) for _ in range(N+1)]
    dp[0][0] = 1
    # morau
    for i, a in enumerate(A):            
        for j in range(S+1):
            if j >= a:
                dp[i+1][j] = 2 * dp[i][j]
                dp[i+1][j] %= MOD
                dp[i+1][j] += dp[i][j-a]
                dp[i+1][j] %= MOD
            else:
                dp[i+1][j] = 2 * dp[i][j]
                dp[i+1][j] %= MOD
                

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

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)]
#i個目までの和がjの数となるのは何通りあるかdp[i][j]
dp[0] = 1
#dp = [0 if i==0 else INF for i in range(S + 1)]

for i in range(N): #i個目まで見て。
  p = [0 for _ in range(S+1)]
  p,dp = dp,p
  for j in range(S+1):
    dp[j] = (dp[j]+p[j]*2)%MOD
    if j >= A[i]:
      #print(j,A[i],p[j-A[i]])
      dp[j] += p[j-A[i]]
  #print(dp)
ans = dp[S]%MOD
print(ans)

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 = pre * 2
    dp[e:] += pre[:-e]
    dp %= mod

ans = dp[s]
print(ans)

Submission status: Accepted

Solution code:
mod = 998244353

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

a.sort()

while a[-1] > s:
    a.pop(-1)
    if a == []:
        print(0)
        exit()

dp = [0] * (s + 1)
dp[0] = 1
for i in a:
    newdp = [2 * j for j in dp]
    for j in range(s - i + 1):
        newdp[j+i] += dp[j]
    dp = newdp

print(dp[s] * pow(2, n - len(a), mod) % mod)

Submission status: Accepted

Solution code:
mod = 998244353

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

a.sort()

while a[-1] > s:
    a.pop(-1)
    if a == []:
        print(0)
        exit()

su = sum(a)
if su < s:
    print(0)
    exit()
if su == s:
    print(pow(2, n - len(a), mod))
    exit()

dp = [0] * (s + 1)
dp[0] = 1
for i in a:
    newdp = [2 * j for j in dp]
    for j in range(s - i + 1):
        newdp[j+i] += dp[j]
    dp = newdp

print(dp[s] * pow(2, n - len(a), mod) % mod)

Submission status: Accepted

Solution code:
def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 998244353
    dp = [[0] * (S+5) for _ in range(N+5)]
    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])



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
MOD = 998244353
def main():
    input = sys.stdin.readline
    N, S = map(int, input().split())
    *A, = map(int, input().split())
    # dp[i][j]=i番目まで見て合計がjになる組み合わせの数
    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 k in range(S + 1):
            # i番目を使わない
            dp[i][k] = (dp[i][k] + dp[i - 1][k] * 2) % MOD
            # i番目を使う
            if k >= a:
                dp[i][k] = (dp[i][k] + dp[i - 1][k - a]) % MOD
    print(dp[N][S])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S, A):
    mod = 998244353
    memo = [0] * (S+1)
    memo[0] = 1
    for a in A:
        nm = [2*memo[s] % mod for s in range(S+1)]
        for s in range(S+1-a):
                nm[s+a] += memo[s]
                nm[s+a] %= mod
        memo = nm

    return memo[S]


def main():
    N, S = read_int_n()
    A = read_int_n()
    print(slv(N, S, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 998244353
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def egcd(a: int, b: int):
    """
    A solution of ax+by=gcd(a,b). Returns
    (gcd(a,b), (x, y)).
    """
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x


def modinv(a: int, mod: int = 10**9 + 7):
    """
    Returns a^{-1} modulo m.
    """
    g, x, y = egcd(a, mod)
    if g > 1:
        raise Exception('{}^(-1) mod {} does not exist.'.format(a, mod))
    else:
        return x % mod


import numpy as np


def main():
    N, S = geta(int)
    A = list(geta(int))
    A.sort()
    mod = 998244353

    inv2 = modinv(2, mod)

    dp = np.zeros((N + 1, S + 1), dtype=np.int64)

    _t = pow(2, N, mod)
    dp[:, 0] = _t
    for i in range(1, N + 1):
        dp[i, :] = dp[i - 1, :]
        if A[i - 1] <= S:
            tmp = np.roll(dp[i - 1, :], A[i - 1])
            tmp[:A[i - 1]] = 0
            dp[i, :] += tmp * inv2
            dp[i, :] %= mod

    print(dp[N][S])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def egcd(a: int, b: int):
    """
    A solution of ax+by=gcd(a,b). Returns
    (gcd(a,b), (x, y)).
    """
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x


def modinv(a: int, mod: int = 10**9 + 7):
    """
    Returns a^{-1} modulo m.
    """
    g, x, y = egcd(a, mod)
    if g > 1:
        raise Exception('{}^(-1) mod {} does not exist.'.format(a, mod))
    else:
        return x % mod


def main():
    N, S = geta(int)
    A = list(geta(int))
    A.sort()
    mod = 998244353

    inv2 = modinv(2, mod)

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

    _t = pow(2, N, mod)
    for n in range(N + 1):
        dp[n][0] = _t

    for i in range(1, N + 1):
        for j in range(1, S + 1):
            if j >= A[i - 1]:
                dp[i][j] = dp[i - 1][j - A[i - 1]] * inv2 + dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j]

            dp[i][j] %= mod

    print(dp[N][S])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    MOD = 998244353
    N, S = map(int, rl().split())
    A = list(map(int, rl().split()))
    
    dp = [[0] * 3010 for _ in range(3010)]
    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])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

def calc():
  mod=998244353
  n,s=map(int,input().split())
  arr=list(map(int,input().split()))
  dp=[0]*(s+1)
  dp[0]=1
  ans=0
  for i in range(1,n+1):
    val=arr[i-1]
    for k in range(s,-1,-1):
      dp[k]*=2
      dp[k]%=mod
      if k>=val and dp[k-val]!=0:
        dp[k]+=dp[k-val]
        dp[k]%=mod
  print(dp[s]%mod)
calc()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
mod = 998244353

n,s = map(int,readline().split())
a = list(map(int,readline().split()))
d = np.zeros(3001, np.int64)
d[0] = 1
for i in a:
  dd = [0]*i + list(d)
  d = d*2
  d += dd[:3001]
  d %= mod
print(d[s])

Submission status: Accepted

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

dp = [[0 for j in range(S+1)] for i in range(N+1)] #dp[i][j] = i番目まで見て重さjのものを取る方法
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

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

print(dp[N][S])            

# print(dp)

Submission status: Accepted

Solution code:
import sys
import math
def input():
    return sys.stdin.readline()[:-1]
mod = 998244353
n,s=map(int,input().split())
a = list(map(int,input().split()))
dp =[[0 for i in range(s+1)]for j in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    for j in range(s+1):
        if j-a[i-1]>=0:
            dp[i][j] += dp[i-1][j-a[i-1]]
            dp[i][j] %= mod

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

print(dp[n][s])

Submission status: Accepted

Solution code:
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(1,N+1):
    dp[i][0] = dp[i-1][0]*2%mod

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

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

Submission status: Accepted

Solution code:
import numpy as np
def main():
    n,s=map(int,input().split())
    A=list(map(int,input().split()))
    dp=np.array([0 for i in range(s+1)])
    dp[0]=1
    for ai in A:
        tmp=dp[:-ai].copy()
        #print(tmp)
        dp*=2
        dp[ai:]+=tmp
        dp%=998244353
    print(dp[s])
    

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
def main():
    n,s=map(int,input().split())
    A=list(map(int,input().split()))
    dp=np.array([0 for i in range(min(3001,s+1))])
    dp[0]=1
    for ai in A:
        tmp=dp[:-ai].copy()
        #print(tmp)
        dp*=2
        dp[ai:]+=tmp
        dp%=998244353
    print(dp[s])
    

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

Submission status: Accepted

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

# dp[i][j] = i番目まで見て和がjとなるような場合の数
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, sep='\n')
print(dp[n][s])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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[i][j]: i 番目の要素を見たとき、和が j であるような場合の数
    dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
    dp[0][0] = 1  # インデックスの集合が空のとき、和は 0 の 1 通り
    for i, a in enumerate(A):
        for j in range(S + 1):
            # editorial でいうところの選択肢 2, 3 に相当するので、2 倍
            dp[i + 1][j] += 2 * dp[i][j]
            dp[i + 1][j] %= MOD
            if j + a <= S:  # 選択肢 1
                dp[i + 1][j + a] += dp[i][j]
                dp[i + 1][j + a] %= MOD
    return dp[N][S]

print(f_knapsack_for_all_subsets())

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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