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 python
#pyrival orz
import os
import sys
from io import BytesIO, IOBase

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

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

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

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

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

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

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


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


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

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

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

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

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

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

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

print(dp[s] % mod)

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

MOD = 998244353

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

U = 3010

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

print(f[S])

Submission status: Runtime Error

Solution code:
import sys

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


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(N)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, left, right):
        """
        [left, right)のsegfuncしたものを得る
        left: index(0-index)
        right: index(0-index)
        """
        res = self.ide_ele
        left += self.num
        right += self.num
        while left < right:
            if left & 1:
                res = self.segfunc(res, self.tree[left])
                left += 1
            if right & 1:
                res = self.segfunc(res, self.tree[right - 1])
            left >>= 1
            right >>= 1
        return res


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 = [SegTree([0] * n, lambda x, y: x + y, 0) for _ in range(s + 1)]
    cnt_num[0].update(0, 1)
    for i in range(1, n + 1):
        a = A[i - 1]
        for j in range(s + 1):
            dp[i][j] += cnt_num[j].query(0, i)
            if a + j > s:
                continue
            dp[i][a + j] += cnt_num[j].query(0, i)
            dp[i][a + j] %= mod
        for k in range(s + 1):
            cnt_num[k].update(i, dp[i][k])

    res = 0
    for i in range(1, n + 1):
        res += dp[i][-1]
        res %= mod
    print(res)


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

Submission status: Runtime Error

Solution code:
def solve():
    N = int(input())
    A = [0]*N
    B = [0]*N
    for i in range(N):
        A[i],B[i] = map(int, input().split())
    A.sort()
    B.sort(reverse=True)
    if N%2==1:
        mid = (N+1)//2-1
        ans = B[mid]-A[mid]+1
    else:
        mid1 = N//2-1
        mid2 = N//2
        ans = (B[mid1]+B[mid2])-(A[mid1]+A[mid2])+1
    return ans
print(solve())

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#import  sys
#input=sys.stdin.readline
#sys.setrecursionlimit(1000000)
mod=int(998244353)
#I=lambda: map(int,input().split())

n,m=map(int,input().split())
a=[int(x) for x in input().split()]
dp={}
def cal(n,s):
    if s<0:
        return 0
    if n<0:
        if s==0:
            return 1
        return 0
    if (n,s) in dp:
        return dp[(n,s)]
    r=cal(n-1,s)*2
    r+=cal(n-1,s-a[n])
    r%=mod
    dp[(n,s)]=r
    return r

ans=cal(n-1,m)
print(ans)

Submission status: Runtime Error

Solution code:
import  sys
input=sys.stdin.readline
#sys.setrecursionlimit(1000000)
mod=int(998244353)
#I=lambda: map(int,input().split())

n,m=map(int,input().split())
a=[int(x) for x in input().split()]
dp={}
def cal(n,s):
    if s<0:
        return 0
    if n<0:
        if s==0:
            return 1
        return 0
    if (n,s) in dp:
        return dp[(n,s)]
    r=cal(n-1,s)*2
    r+=cal(n-1,s-a[n])
    r%=mod
    dp[(n,s)]=r
    return r

ans=cal(n-1,m)
print(ans)

Submission status: Runtime Error

Solution code:
import  sys
#input=sys.stdin.readline
#sys.setrecursionlimit(1000000)
mod=int(998244353)
I=lambda: map(int,input().split())

n,m=I()
a=[int(x) for x in input().split()]
dp={}
def cal(n,s):
    if s<0:
        return 0
    if n<0:
        if s==0:
            return 1
        return 0
    if (n,s) in dp:
        return dp[(n,s)]
    r=cal(n-1,s)*2
    r+=cal(n-1,s-a[n])
    r%=mod
    dp[(n,s)]=r
    return r

ans=cal(n-1,m)
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
import bisect
import math
import numpy as np
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])

Submission status: Runtime Error

Solution code:
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] + (j - ai >= 0) * dp[j - ai]) % MOD
 
print(dp[S])

Submission status: Runtime Error

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import numpy as np

def main():
	n,s=MI()
	A=LI()

	li=[0]*(s+10)
	li=np.array(li)
	li[0]=1
	#print(li)

	for i in A:
		tmp=li.copy()
		li*=2
		if i<n:
			li[i:]+=tmp[:s+10-i]
		li%=998244353
		#print(li)
	print(li[s])



if __name__ == "__main__":
	main()

Submission status: Runtime Error

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import numpy as np

def main():
	n,s=MI()
	A=LI()

	li=[0]*(s+10)
	li=np.array(li)
	li[0]=1
	#print(li)

	for i in A:
		tmp=li.copy()
		li*=2
		li[i:]+=tmp[:s+10-i]
		li%=998244353
		#print(li)
	print(li[s])



if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
EPS = 10**(-9)
def is_equal(a,b):
    return abs(a-b) < EPS

def norm(v,i):
    import math
    ret = 0
    n = len(v)
    for j in range(n):
        ret += abs(v[j])**i
    return math.pow(ret,1/i)

class Vector(list):
    """
    ベクトルクラス
    対応演算子
    +  : ベクトル和 
    -  : ベクトル差
    *  : スカラー倍、または内積
    ** : 外積
    += : ベクトル和
    -= : ベクトル差
    *= : スカラー倍
    /= : スカラー倍

    メソッド
    self.norm(i) : L{i}ノルムを計算
    """
    def __add__(self,other):
        n = len(self)
        ret = [0]*n
        for i in range(n):
            ret[i] = super().__getitem__(i) + other.__getitem__(i)
        return self.__class__(ret)
    
    def __radd__(self,other):
        n = len(self)
        ret = [0]*n
        for i in range(n):
            ret[i] = other.__getitem__(i) + super().__getitem__(i)
        return self.__class__(ret)
    
    def __iadd__(self, other):
        n = len(self)
        for i in range(n):
            self[i] += other.__getitem__(i)
        return self

    def __sub__(self,others):
        n = len(self) 
        ret = [0]*n
        for i in range(n):
            ret[i] = super().__getitem__(i) - others.__getitem__(i)
        return self.__class__(ret)

    def __iadd__(self, other):
        n = len(self)
        for i in range(n):
            self[i] -= other.__getitem__(i)
        return self

    def __rsub__(self,others):
        n = len(self) 
        ret = [0]*n
        for i in range(n):
            ret[i] = others.__getitem__(i) - super().__getitem__(i)
        return self.__class__(ret)
    
    def __mul__(self,other):
        n = len(self)
        if isinstance(other,list):
            ret = 0
            for i in range(n):
                ret += super().__getitem__(i)*other.__getitem__(i)
            return ret
        else:
            ret = [0]*n
            for i in range(n):
                ret[i] = super().__getitem__(i)*other
            return self.__class__(ret)

    def __rmul__(self,other):
        n = len(self)
        if isinstance(other,list):
            ret = 0
            for i in range(n):
                ret += super().__getitem__(i)*other.__getitem__(i)
            return ret
        else:
            ret = [0]*n
            for i in range(n):
                ret[i] = super().__getitem__(i)*other
            return self.__class__(ret)
    
    
    def __truediv__(self,other):
        """
        ベクトルのスカラー除法
        Vector/scalar
        """
        n = len(self)
        ret = [0]*n
        for i in range(n):
            ret[i] = super().__getitem__(i)/other
        return self.__class__(ret)
    
    def norm(self,i):
        """
        L{i}ノルム
        self.norm(i)
        """
        return norm(self,i)
    
    def __pow__(self,other):
        """
        外積
        self**other
        """
        n = len(self)
        ret = [0]*3
        x = self[:]
        y = other[:]
        if n == 2:
            x.append(0)
            y.append(0)
        if n == 2 or n == 3:
            for i in range(3):
                ret[0],ret[1],ret[2] = x[1]*y[2]-x[2]*y[1],x[2]*y[0]-x[0]*y[2],x[0]*y[1]-x[1]*y[0]
            ret = Vector(ret)
            if n == 2:
                return ret.norm(2)
            else:
                return ret

N,S = map(int,input().split())
A = list(map(int,input().split()))
coefs = Vector([0]*(S+1))
coefs[0] = 1

for i in range(N):
    tmp = Vector(coefs[:])
    coefs = coefs*2
    coefs[A[i]:] += Vector(tmp[:S-A[i]+1])
print(coefs[-1])

Submission status: Runtime Error

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


def main():
    n, s = map(int, input().split())
    A = [int(i) for i in input().split()]

    MOD = 998244353

    dp = np.zeros(s + 1, dtype="int32")
    dp[0] = 1

    for a in A:
        p = (dp * 2) % MOD
        p %= MOD
        p[a:] += dp[:a]
        dp = p % MOD

    print(dp[s])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(3000)

def test(a,s,i):
    if i==len(a) or a[i]>s : return []
    if a[i]==s:return [[i]]
    else: return [[i]+x for x in test(a,s-a[i],i+1)]+test(a,s,i+1)
        

n,s=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a)
l=test(a,s,0)
out=0
for s in l:
    out+=2**(len(a)-len(s))
print(out%998244353)

Submission status: Runtime Error

Solution code:
def test(a,s,i):
    if i==len(a) or a[i]>s : return []
    if a[i]==s:return [[i]]
    else: return [[i]+x for x in test(a,s-a[i],i+1)]+test(a,s,i+1)
        

n,s=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a)
l=test(a,s,0)
out=0
for s in l:
    out+=2**(len(a)-len(s))
print(out)

Submission status: Runtime Error

Solution code:
def test(a,s,i):
    if i==len(a) or a[i]>s : return []
    if a[i]==s:return [[i]]
    else: return [[i]+x for x in test(a,s-a[i],i+1)]+test(a,s,i+1)
        

n,s=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a)
print(a)
l=test(a,s,0)
print(l)
out=0
for s in l:
    out+=2**(len(a)-len(s))
print(out)

Submission status: Runtime Error

Solution code:
import numpy as np
p = 998244353

N,S = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
dp = np.zeros(S+1)
dp[0] = 1
for a in A:
  if S < a:
    dp = 2*dp
    continue
  tmp = 2*dp
  dp = np.append(np.zeros(a),dp[:S-a+1])
  dp += tmp
  dp %= p
print(int(dp[S]))

Submission status: Runtime Error

Solution code:
def abc(l,n,s,i,x,b):
    try:
        return d[i,x,b]
    except:
        pass
    if x>s:
        return 0
    if i==n:
        return (x==s)*pow(2,b)
    ans=(abc(l,n,s,i+1,x,b+1)+abc(l,n,s,i+1,x+l[i],b))%mod
    d[i,x,b]=ans
    return ans
n,s=map(int,input().split())
l=list(map(int,input().split()))
d={}
mod=998244353
print(abc(l,n,s,0,0,0))

Submission status: Runtime Error

Solution code:
def resolve():
    n, s = map(int, input().split())
    a = list(map(int,input().split()))
    dp = [[0]*(s+10) for _ in range(n+10)]
    dp[0][0] = 1
    mod = 998244353
    for i in range(1,n+1):
        nexta = a[i-1]
        for j in range(0, s+1):
            dp[i][j] += (2 * dp[i - 1][j])% mod
            if j + nexta > s:
                continue
            else:
                dp[i][j+nexta] += (dp[i-1][j])%mod
    print((dp[n][s])%mod)
resolve(()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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


N = int(readline())
AB = np.array(read().split(), np.int64)

A = AB[::2]
B = AB[1::2]

A.sort()
B.sort()

if N % 2 == 0:
    n = N // 2
    med1 = A[n - 1] + A[n]
    med2 = B[n - 1] + B[n]
    x = med2 - med1 + 1
else:
    n = N // 2
    med1 = A[n]
    med2 = B[n]
    x = med2 - med1 + 1

print(x)

Submission status: Runtime Error

Solution code:
(n, s), *a = [[*map(int, t.split())] for t in open(0)]
a = a[0]
mem = [0] * (n + 1)
mem[0] = 1

for x in a:
    tmp = [2 * e for e in mem]
    if x <= s:
        for i in range(s - x + 1):
            tmp[i + x] += mem[i]
    mem = tmp
print(mem[s])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

def _fmt(A, inverse = False):
    N = len(A)
    logN = (N - 1).bit_length()
    base = pow(3, (MOD - 1) // N * (1 - 2 * inverse) % (MOD - 1), MOD)
    step = N
    for k in range(logN):
        step >>= 1
        w = pow(base, step, MOD)
        wj = 1
        nA = [0] * N
        for j in range(1 << k):
            for i in range(1 << logN - k - 1):
                s, t = i + j * step, i + j * step + (N >> 1)
                ps, pt = i + j * step * 2, i + j * step * 2 + step
                nA[s], nA[t] = (A[ps] + A[pt] * wj) % MOD, (A[ps] - A[pt] * wj) % MOD
            wj = (wj * w) % MOD
        A = nA
    return A

def convolution(f, g):
    N = 1 << (len(f) + len(g) - 2).bit_length()
    Ff, Fg = _fmt(f + [0] * (N - len(f))), _fmt(g + [0] * (N - len(g)))
    N_inv = pow(N, MOD - 2, MOD)
    fg = _fmt([a * b % MOD * N_inv % MOD for a, b in zip(Ff, Fg)], inverse = True)
    del fg[len(f) + len(g) - 1:]
    return fg

def resolve():
    n, s = map(int, input().split())
    F = [None] * n
    for i, a in enumerate(map(int, input().split())):
        tmp = [0] * a
        tmp[0] = 2
        tmp.append(1)
        F[i] = tmp
    logN = (n - 1).bit_length()
    N = 1 << logN
    F += [[1] for _ in range(N - len(F))]

    for i in range(logN):
        nF = [None] * (1 << logN - i - 1)
        for i in range(1 << logN - i - 1):
            nF[i] = convolution(F[2 * i], F[2 * i + 1])[:s + 1]
        F = nF
    print(F[0][s])
resolve()

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
import numpy as np
N,S = map(int,input().split())
MOD = 998244353
A = list(map(int,input().split()))
dp = np.zeros(S+1,dtype = np.int64)
dp[0] = 2
if A[0] <= S:
    dp[A[0]] = 1
for i in range(1,N):
    a = A[i]
    p = (dp*2) %= MOD
    if a > S:
        continue
    else:
        p[a:] += dp[:-a]
    dp = p % MOD
print(dp[-1])

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
import numpy as np
N,S = map(int,input().split())
MOD = 998244353
A = list(map(int,input().split()))
dp = [[0]*(S+1) for _ in range(N)]
if A[0] <= S:
    dp[0][A[0]] = 1
dp[0][0] = 2
for i in range(1,N):
    a = A[i]
    for j in range(S+1):
        dp[i][j] += 2*dp[i-1][j] % MOD
        if j - a < 0:
            continue
        else:
            dp[i][j] += dp[i-1][j-a]
        dp[i][j] %= MOD
print(dp[N-1][S])

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]

N,S = map(int,input().split())
MOD = 998244353
A = list(map(int,input().split()))
dp = np.zeros(N)
if A[0] <= S:
    dp[0][A[0]] = 1
dp[0][0] = 2
for i in range(1,N):
    a = A[i]
    for j in range(S+1):
        dp[i][j] += 2*dp[i-1][j] % MOD
        if j - a < 0:
            continue
        else:
            dp[i][j] += dp[i-1][j-a]
        dp[i][j] %= MOD
print(dp[N-1][S])

Submission status: Runtime Error

Solution code:
import numpy as np
n,s,*a=map(int,open(0).read().split())
mod=998244353
d=np.zeros(s+1,dtype=np.int64)
d[0]=1
for x in a:
	p=d*2
	p[x:]+=d[:s-x+1]
	p%=mod
	d=p
print(d[-1])

Submission status: Runtime Error

Solution code:
import sys

import numpy as np

MOD = 998244353

def main():
    N, S = map(int, input().split())
    X = [int(x) for x in sys.stdin.readline().split()]

    # dp = np.zeros((N+1)*(S+1), dtype=np.int).reshape((N+1),(S+1))
    dp = [[0 for _ in range(S+1)] for _ in range(N+1)]

    dp[0][0] = 1

    for i in range(N):
        xi = X[i]
        # xi を U に加えない場合
        for j in range(S+1):
            dp[i+1][j] += dp[i][j]*2  # T に加える／加えない
            dp[i+1][j] %= MOD
            # xi を U に加える場合
            if j+xi > S: continue
            dp[i+1][j+xi] += dp[i][j]
            dp[i+1][j+xi] %= MOD

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

main()

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys
MOD = 998244353


@lru_cache(maxsize=3100)
def pow_mod(i):
    # pow(2, i - 1, MOD)
    if i == 1:
        return 1
    else:
        return pow_mod(i - 1) * 2 % MOD


def main():
    input = sys.stdin.buffer.readline
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[None] * (s + 1) for _ in range(n + 1)]
#     dp[i][j]:=集合{1..i}の空でない部分集合T全てについて,和がjとなる部分集合の個数の和
    for i in range(n + 1):
        for j in range(s + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
                continue
            if j > a[i - 1]:
                dp[i][j] = dp[i - 1][j] * 2 + dp[i - 1][j - a[i - 1]]
            elif j == a[i - 1]:
                dp[i][j] = dp[i - 1][j] * 2 + pow_mod(i)
            else:
                dp[i][j] = dp[i - 1][j] * 2
            dp[i][j] %= MOD
    print(dp[n][s])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys
MOD = 998244353


@lru_cache(maxsize=None)
def pow_mod(i):
    # pow(2, i - 1, MOD)
    if i == 1:
        return 1
    else:
        return pow_mod(i - 1) * 2 % MOD


def main():
    input = sys.stdin.buffer.readline
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[None] * (s + 1) for _ in range(n + 1)]
#     dp[i][j]:=集合{1..i}の空でない部分集合T全てについて,和がjとなる部分集合の個数の和
    for i in range(n + 1):
        for j in range(s + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
                continue
            if j > a[i - 1]:
                dp[i][j] = dp[i - 1][j] * 2 + dp[i - 1][j - a[i - 1]]
            elif j == a[i - 1]:
                dp[i][j] = dp[i - 1][j] * 2 + pow_mod(i)
            else:
                dp[i][j] = dp[i - 1][j] * 2
            dp[i][j] %= MOD
    print(dp[n][s])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, S = map(int, input().split())
As = list(map(int, input().split()))
mod = 998244353
import numpy as np
dp = np.array([[0]*(S+1) for i in range(N+1)])
dp[0][0] = 1
for i in range(1, N+1):
    a = As[i-1]
    for s in range(S+1):
        if s-a>=0:
            dp[i][s] += (dp[i-1][s-a] + dp[i-1][s]*2)
        else:
            dp[i][s] += (dp[i-1][s]*2)
    dp[i] %= mod
print(dp[-1][-1]%mod)

Submission status: Runtime Error

Solution code:
import numpy as np

print(1)

Submission status: Runtime Error

Solution code:
MOD = 998244353
N, S = map(int, input().split())
A = tuple(map(int, input().split()))
table = {0: 1}
for n in range(N):
    next_table = dict()
    for s, now in table.items():
        next_table[s] = (next_table.get(s, 0) + now * 2) % MOD
        if s + A[n] <= S:
            next_table[s + A[n]] = (next_table.get(s + A[n], 0) + now) % MOD
    table = next_table
print(table[S])