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:
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 ss in range(s+1):
        if(ss >= a[i]):
            dp[i+1][ss] = (dp[i][ss]*2 + dp[i][ss-a[i]])%MOD #非常に大きな数になると考えられるため先にMOD計算を行う
        else:
            dp[i+1][ss] = dp[i][ss]*2 % MOD

print(dp[n][s])

Submission status: Accepted

Solution code:
import numpy as np

mod = 998244353
n, s = map(int, input().split())
dp = np.zeros(s+1, dtype=int)
dp[0] = 1
for a in map(int, input().split()):
  pre_dp = dp
  dp = pre_dp * 2 % mod
  dp[a:] = (dp[a:] + pre_dp[:-a]) % mod
print(dp[-1])

Submission status: Accepted

Solution code:
import numpy as np

mod = 998244353
n, s = map(int, input().split())
dp = np.zeros((n+1, s+1), dtype=int)
dp[0, 0] = 1
for i, a in enumerate(map(int, input().split())):
  dp[i+1] = dp[i] * 2 % mod
  dp[i+1][a:] = (dp[i+1][a:] + dp[i][:-a]) % mod
print(dp[-1, -1])

Submission status: Accepted

Solution code:
N, S = map(int, input().split())
As = list(map(int, input().split()))

P = 998244353

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

for i in range(N+1):
  memo[0][i] = (2**i) % P

for i, a in enumerate(As):
  for j in range(S+1):
    if j - a < 0:
      memo[j][i+1] = memo[j][i]*2 % P
    else:
      memo[j][i+1] = (memo[j][i]*2 + memo[j-a][i]) % P

print(memo[S][N])

Submission status: Accepted

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

# dp[i][j]:Aをi番目まで見たときに、和がjとなるTの個数。
dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
  ai = a[i]
  for j in range(s+1):
    dp[i+1][j] += 2*dp[i][j] #aiを選ぶか選ばないかの2通りある。
    dp[i+1][j] %= MOD
    if j+ai <= s:
      dp[i+1][j+ai] += dp[i][j]
      dp[i+1][j+ai] %= MOD
print(dp[n][s])
#print(dp)

Submission status: Accepted

Solution code:
import numpy as np
MOD = 998244353

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

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]*(s+1)
dp[0] = pow(2, n, MOD)
inv_2 = pow(2, MOD-2, MOD)
for a in A:
    for j in reversed(range(s+1)):
        if s < j+a:
            continue
        dp[j+a] += dp[j]*inv_2
        dp[j+a] %= MOD

print(dp[-1] % MOD)

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_2 = pow(2, MOD-2, MOD)
for a in A:
    for j in reversed(range(s+1)):
        if s < j+a:
            continue
        dp[j+a] += dp[j]*inv_2 % MOD

print(dp[-1] % MOD)

Submission status: Accepted

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
# dp[n][i][s] := i 番目まで見て n 個使って合計が s になる場合の数 これは無理
# dp[i][s] := i 番目まで見て合計 s 
dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
mod = 998244353
for i, a in enumerate(A, 1):
    for s in range(S+1):
        if s-a >= 0:
            dp[i][s] = (dp[i-1][s] * 2 + dp[i-1][s-a]) % mod
        else:
            dp[i][s] = dp[i-1][s] * 2 % mod
print(dp[N][S])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
N,S = map(int,readline().split())
A = list(map(int,readline().split()))
dp = [[0]*(S+2) for i in range(N+1)]
dp[0][0] = 1
mod = 998244353
for i,a in enumerate(A):
    for j in range(S+1):
        if j-a >= 0:
            dp[i+1][j] = (dp[i][j]*2+dp[i][j-a])%mod
        else:
            dp[i+1][j] = dp[i][j]*2%mod
print(dp[N][S])

Submission status: Accepted

Solution code:
import numpy as np

MOD = 998244353

N, S = map(int, input().split(' '))
A = (0, *map(int, input().split(' ')))

dp = np.zeros(shape=(N + 1, S + 1), dtype=int)
dp[0][0] = 1

for i in range(1, N + 1):
    a = A[i]
    dp[i] = 2 * dp[i - 1] % MOD
    dp[i][a:] += dp[i - 1][:-a]
    dp[i] %= MOD

print(dp[N][S])

Submission status: Accepted

Solution code:
mod = 998244353

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

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

print(dp[S])

Submission status: Accepted

Solution code:
mod = 998244353

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

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

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

print(dp[N][S])

Submission status: Accepted

Solution code:
import numpy as np
import numba
from typing import List


@numba.jit
def solver(N: int, S: int, A: np.array) -> int:
    dp = np.zeros((N+1, S+1), dtype=np.int64)

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


def main():
    N, S = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    ans = solver(N, S, np.array(A))
    print(ans)
 
 
if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    import numpy as np
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N, S = [int(x) for x in input().strip().split()]
    An = [int(x) for x in input().strip().split()]
    dp = np.zeros((S+1), dtype=int)
    dp[0] = 2
    if An[0] <= S:
        dp[An[0]] = 1

    for n in range(1, N):
        dp *= 2
        dp[An[n]:] += dp[:-An[n]] // 2
        dp %= 998244353

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

Submission status: Accepted

Solution code:
import sys

import numpy as np

input = lambda: sys.stdin.readline().rstrip()
MOD = 998244353

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

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

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

for i in range(N):
    for j in range(S+1):
        if dp[i][j] != 0:
            dp[i+1][j] += dp[i][j] * 2
            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
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=998244353
    N,S=MI()
    A=LI()
    dp=[[0]*(S+1) for _ in range(N+1)]
    #dp[i][j]はi番目までで，和がjになるのが何個作れるか．
    #ただし，その数を使わない場合，選択するかしないか選べるのでダブルでカウント
    
    dp[0][0]=1
    
    
    for i in range(N):
        #dp[i][0]+=1
        for j in range(S+1):
            dp[i+1][j]+=dp[i][j]*2
            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[-1][-1])
    

            

main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10**9)
mod = 998244353

def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    
    """
    maspyさんの多項式解法も試してみる。
    例えばA = [2, 2, 4]の場合、
        f({1, 2, 3}) = [x^S](1 + x^2)(1 + x^2)(1 + x^4)
        f({1, 2})    = [x^S](1 + x^2)(1 + x^2)
    よって求める答えはf_i = (1 + x^{A[i]})として
        [x^S](f_1 f_2 f_3 + f_1 f_2 + f_2 f_3 + f_3 f_1 + f_1 + f_2 + f_3)
    となる。
    さらにS >= 1なのでこれに1を足しても結果は変わらない。なので因数分解して
        [x^S](1 + f_1)(1 + f_2)(1 + f_3)
    を求めればよい。
    """

    poly = [0] * (S + 1) # poly[i] = (x^iの係数)
    poly[0] = 1
    for a in A:
        # poly *= (2 + x^a)
        poly2 = [poly[i] * 2 % mod for i in range(S + 1)]
        for i in range(S + 1):
            if i + a <= S:
                poly2[i + a] += poly[i]
                poly2[i + a] %= mod
        poly = poly2
    print(poly[S])
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
import random
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=998244353
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

dp=[[0]*(s+1) for i in range(n+1)]
dp[0][0]=1

for i in range(n):
    for 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
input = sys.stdin.readline
import numpy as np
from numba import njit


def read():
    N, S = map(int, input().strip().split())
    A = np.fromstring(input().strip(), dtype=np.int32, sep=" ")
    return N, S, A


@njit
def solve(N, S, A, MOD=998244353):
    dp = np.zeros((S+1), dtype=np.int32)
    dp[0] = 1
    for i in range(N):
        for j in range(S, -1, -1):
            v = 2 * dp[j]
            if j - A[i] >= 0:
                v += dp[j-A[i]]
            dp[j] = v % MOD
    return dp[S]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 998244353
INF = 10 ** 15
import numpy as np

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

    dp = np.zeros(S + 1,np.int64)
    dp[0] = pow(2,N,MOD)
    inv2 = pow(2,MOD - 2,MOD)
    for a in A:
        dp[a:] = np.mod(dp[a:] + dp[:-a] * inv2,MOD)
    print(dp[S])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
from functools import lru_cache
sys.setrecursionlimit(10**9)
mod = 998244353

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

    """
    再帰の計算式自体は合っていた！
    メモ化再帰とdpで計算量は変わらないはずだが、取りあえずdpで書き直してみる。
    """

    dp = [[0] * (S + 1) for _ in range(N)] # dp[n][s] = (N=n, S=sに対する問題の解)
    dp[0][0] = 1
    for n in range(1, N): dp[n][0] = (dp[n - 1][0] * 2 + 1) % mod
    for s in range(1, S + 1): dp[0][s] = 1 if s == A[0] else 0
    for n in range(1, N):
        for s in range(1, S + 1):
            dp[n][s] = (dp[n - 1][s] * 2 + dp[n - 1][s - A[n]]) if s >= A[n] else dp[n - 1][s] * 2
            if A[n] == s: dp[n][s] += 1
            dp[n][s] %= mod
    print(dp[N - 1][S])

    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 998244353
INF = 10 ** 15

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

    dp = [0] * (1 + S)
    dp[0] = pow(2,N,MOD)
    inv2 = pow(2,MOD - 2,MOD)
    for a in A:
        for s in range(S,a - 1,-1):
            dp[s] = (dp[s] + dp[s - a] * inv2)%MOD
    print(dp[S])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 998244353
INF = float('inf')


N, A = MI()
a = [0, *list(map(int, input().split()))]

# dp[i][j] := i番目までの数字を使って総和をjとする場合の数
# dp[i][j] = dp[i - 1][j - a[i]] + dp[i - 1][j]
dp = [[0] * (A + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i in range(1, N + 1):
    for j in range(A + 1):
        if j - a[i] < 0:  # j - a[i] が負の数になってしまう時はa[i]を使用することはできない
            dp[i][j] = 2 * dp[i - 1][j] % MOD
            continue
        dp[i][j] = (dp[i - 1][j - a[i]] + 2 * dp[i - 1][j]) % MOD
print(dp[N][A])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 998244353
INF = 10 ** 15

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

    dp = [[0]*(1 + S) for _ in range(N + 1)]
    dp[0][0] = pow(2,N,MOD)
    inv2 = pow(2,MOD - 2,MOD)
    for i,a in enumerate(A):
        for j in range(S + 1):
            if j < a:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = (dp[i][j] + dp[i][j - a] * inv2)%MOD
    print(dp[N][S])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
#import numpy as np
import re
import math
from collections import defaultdict
from collections import deque
import collections
from fractions import Fraction
import bisect
from queue import PriorityQueue
import itertools
from copy import deepcopy
import random
import time
import os
import sys
import datetime
from functools import lru_cache
from functools import reduce
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
alphabet="abcdefghijklmnopqrstuvwxyz"
numbers="0123456789"
mod=int(10**9+7)
inf=int(10**19)
class Edge():
    def __init__(self,x,y,val=1):
        self.x=x
        self.y=y
        self.val=val
class unionfind():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):
            self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def yn(b):
    if b:print("yes")
    else:print("no")
def Yn(b):
    if b:print("Yes")
    else:print("No")
def YN(b):
    if b:print("YES")
    else:print("NO")
def ispow(a,b):
    now=b
    while now<a:
        now*=b
    return now==a
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n):
    if n==0:return []
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    ret=[]
    for a in range(n+1):
        if(A[a]):ret.append(a)
    return ret
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(bbool,ret1,ret2):
    if bbool:return ret1
    else:return  ret2
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n):
    b = 2
    ret=defaultdict(int)
    while b * b <= n:
        while n % b == 0:
            n //= b
            ret[b]+=1
        b+=1
    if n > 1:ret[n]+=1
    return ret
def pm(x):
    return x//abs(x)
def inputintlist(): 
    return list(map(int,input().split()))
def inputfloatlist(): 
    return list(map(float,input().split()))
def tozero(A):
    ret=[None]*len(A)
    for a in range(len(A)):
        ret[a]=A[a]-1
    return ret
def istanchouzouka(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>=a:
            f=False
        prev=a
    return f
def istanchouhigensyou(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>a:
            f=False
        prev=a
    return f
def getallsum(A):
    s=sum(A)
    dp=defaultdict(int)
    dp[0]=1
    for a in range(0,len(A)):
        for b in range(s,-1,-1):
            if b-A[a]>=0:
                dp[b]+=dp[b-A[a]]
    return dp
def yuukoutomukou(edges):
    ret=deepcopy(edges)
    for edge in edges:
        if not edge.x==edge.y:
            ret.append(Edge(edge.y,edge.x,edge.val))
    return ret
def dijkstra(edges,V,start):
    mincost=[inf]*V
    G=[[] for a in range(V)]
    for edge in edges:
        G[edge.x].append([edge.val,edge.y])
    Q=PriorityQueue()
    Q.put([0,start])#[cost,x]
    while not Q.empty():
        nowcost,nowx=Q.get()
        if mincost[nowx]==inf:
            mincost[nowx]=nowcost
            for cost,y in G[nowx]:
                newcost=nowcost+cost
                Q.put([newcost,y])
    return mincost
def warshallfloyd(edges,V):
    mincost=[[inf for b in range(V)] for a in range(V)]
    for a in range(V):mincost[a][a]=0
    for edge in edges:
        mincost[edge.x][edge.y]=min(mincost[edge.x][edge.y],edge.val)#x→yが複数ある場合のためにmin()する
    for k in range(V):
        for s in range(V):
            for t in range(V):
                if mincost[s][k]==inf or mincost[k][t]==inf:continue
                mincost[s][t]=min(mincost[s][t],mincost[s][k]+mincost[k][t])
    return mincost
def bellemanford(edges,V,start):
    mincost=[inf]*V
    mincost[start]=0
    for _ in range(V):
        for edge in edges:
            if mincost[edge.x]==inf:continue
            mincost[edge.y]=min(mincost[edge.y],mincost[edge.x]+edge.val)
    return mincost
def ruisekiwa(A):
    ret=[0]*(len(A)+1)
    for a in range(len(A)):
        ret[a+1]=ret[a]+A[a]
    return ret
def getmd(x1,y1,x2,y2):
    return abs(x1-x2)+abs(y1-y2)
def geted(x1,y1,x2,y2):
    return math.sqrt((x1-x2)**2+(y1-y2)**2)
class fordfulkerson():
    def __init__(self,edges,V,s,t):
        self.V=V
        self.used=[False]*V
        self.G=[[] for a in range(V)]
        self.s=s
        self.t=t
        for edge in edges:
            self.G[edge.x].append({"x":edge.x,"y":edge.y,"cap":edge.val,"rev":len(self.G[edge.y])})
            self.G[edge.y].append({"x":edge.y,"y":edge.x,"cap":0,"rev":len(self.G[edge.x])-1})
    def dfs(self,v,t,f=inf):
        if v==t:return f
        self.used[v]=True
        for a in range(len(self.G[v])):
            x=self.G[v][a]["x"]
            y=self.G[v][a]["y"]
            cap=self.G[v][a]["cap"]
            rev=self.G[y][self.G[x][a]["rev"]]
            if self.used[y] or cap==0:continue
            f2=self.dfs(y,t,min(f,cap))
            if f2>0:
                self.G[v][a]["cap"]-=f2
                rev["cap"]+=f2
                return f2
        return 0
    def maxflow(self):
        flow=0
        while True:
            self.used=[False]*V
            zouka=self.dfs(self.s,self.t)
            if zouka==0:break
            flow+=zouka
        return flow



######################################################################################################
def f(A,S):
    dp=[[0 for b in range(S+1)] for a in range(len(A)+1)]
    dp[0][0]=1
    for i in range(1,len(A)+1):
        for s in range(S+1):
            dp[i][s]+=dp[i-1][s]*2
            if s-A[i-1]>=0:
                dp[i][s]+=dp[i-1][s-A[i-1]]
            dp[i][s]%=998244353
    return dp
n,S=inputintlist()
A=inputintlist()
dp=f(A,S)
ans=dp[n][S]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
fft = np.fft.rfft
ifft = np.fft.irfft
mod = 998244353

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

dp = np.zeros(U+10, dtype=np.int64)
dp[0] = 1
for a in A:
    newDP = dp.copy() * 2
    newDP[a:] += dp[:-a]
    newDP %= mod
    dp = newDP

print(dp[S])

Submission status: Accepted

Solution code:
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop
import bisect

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

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

mod = 998244353

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

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

#print(DP)

Submission status: Accepted

Solution code:
n,s=map(int,input().split())
*A,=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 A[i]+j<s+1:
            dp[i+1][j+A[i]]+=dp[i][j]
        dp[i+1][j]+=2*dp[i][j]
        dp[i+1][j]%=mod
print(dp[-1][-1])

Submission status: Accepted

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

mod=998244353
#dp[i][j]:i番目まで見て値がjである集合の個数
dp=[[0]*(s+1) for i in range(n+1)]
dp[0][0]=1

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

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

Submission status: Accepted

Solution code:
n,s=map(int,input().split())
*A,=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 A[i]+j<s+1:
            dp[i+1][j+A[i]]=(dp[i+1][j+A[i]]+dp[i][j])%mod
        dp[i+1][j]=(dp[i+1][j]+2*dp[i][j])%mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:
n,s=map(int,input().split())
dp=[0]*(s+1)
dp[0]=1
ne=[0]*(s+1)
mod=998244353
for i in list(map(int,input().split())):

    for k in range(0,s+1):
        if k+i<=s:
            ne[k+i]=(ne[k+i]+dp[k])%mod
        ne[k]=(ne[k]+2*dp[k])%mod
        dp[k]=0
    dp,ne=ne,dp
print(dp[-1])

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, S = iim()
    A = list(iim())
    mod = 998244353
    S1 = S + 1

    dp = [0] * (S+1)

    dp[0] = pow(2, N, mod)
    inv = pow(2, mod-2, mod)

    for ai in A:
        for i in range(S, ai-1, -1):
            dp[i] = (dp[i] + dp[i-ai]*inv) % mod

    print(dp[-1])


if __name__ == "__main__":
    resolve()

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

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

print(dp[s])

Submission status: Accepted

Solution code:
# Import
from collections import deque
import math

# I/O
def read(): return input()
def read_int(): return int(input())
def read_array(type=int): return [type(i) for i in input().split()]
def read_tupple(type=None):
    tmp = input().split()
    if type is None: return map(int, tmp)
    assert len(tmp) == len(type)
    return [type[i](tmp[i]) for i in range(len(tmp))]

MOD = 998244353
N, S = read_tupple()
A = read_array()

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]
        if j - A[i] >= 0:
            dp[i + 1][j] += dp[i][j - A[i]]
        
        while dp[i+1][j] > MOD:
            dp[i+1][j] -= MOD
        
print(dp[N][S])

Submission status: Accepted

Solution code:
# Import
from collections import deque
import math

# I/O
def read(): return input()
def read_int(): return int(input())
def read_array(type=int): return [type(i) for i in input().split()]
def read_tupple(type=None):
    tmp = input().split()
    if type is None: return map(int, tmp)
    assert len(tmp) == len(type)
    return [type[i](tmp[i]) for i in range(len(tmp))]

# Implementation
# class ModInt:
#     def __init__(self, n, MOD):
#         self.n = n
#         self.MOD = MOD
    
#     def __add__(self, o):
#         return ModInt((self.n + o.n) % self.MOD, self.MOD)

#     def __sub__(self, o):
#         return ModInt((self.n - o.n + self.MOD) % self.MOD, self.MOD)

#     def __mul__(self, o):
#         return ModInt((self.n * o.n) % self.MOD, self.MOD)

#     def __iadd__(self, o):
#         self.n = (self.n + o.n) % self.MOD
#         return self

#     def __isub__(self, o):
#         self.n = (self.n - o.n + self.MOD) % self.MOD
#         return self

#     def __imul__(self, o):
#         self.n = (self.n * o.n) % self.MOD
#         return self

#     def __str__(self): return str(self.n)

MOD = 998244353
N, S = read_tupple()
A = read_array()

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

mod = 998244353

pows = [1]
for i in range(10000):
    pows.append((pows[-1] * 2) % mod)

dp = [0] * (s + 1)
dp[0] = 1
if a[0] <= s:
    dp[a[0]] = 1

for i in range(1, n):
    dp_new = [0] * (s + 1)
    dp_new[0] = 1
    for j in range(1, s + 1):
        dp_new[j] = dp[j] * 2

        if j - a[i] > 0:
            dp_new[j] += dp[j-a[i]]
        elif j == a[i]:
            dp_new[j] += pows[i]
        dp_new[j] %= mod

    dp = dp_new

print(dp[-1])

Submission status: Accepted

Solution code:
import numpy as np

def main():
    n, s = map(int, input().split())
    a = [int(i) for i in input().split()]
    mod = 998244353
    dp = np.zeros((n + 1, s + 1), dtype=int)
    dp[0][0] = 1
    for i in range(n):
        ai = a[i]
        dp[i + 1] = dp[i] * 2 % mod
        dp[i + 1, ai:] = (dp[i + 1, ai:] + dp[i, :-ai]) % mod
    print(dp[n][s])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

mod = 998244353

n, s = map(int, input().split())
A = list(map(int, input().split()))
DP = np.zeros(3005, dtype=np.int64)
DP[0] = 1

for a in A:
    double = DP * 2
    double[a:] += DP[:-a]  # shift
    DP = double % mod

print(DP[s])

Submission status: Accepted

Solution code:
import numpy as np

mod = 998244353

n, s = map(int, input().split())
A = list(map(int, input().split()))
DP = np.zeros(3005, dtype=np.int64)
DP[0] = 1

for a in A:
    double = DP * 2
    shift = np.hstack([np.zeros(a), DP[:-a]]).astype(np.int64)
    DP = double + shift
    DP %= mod

print(DP[s])

Submission status: Accepted

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

dp = [[0] * (s+1) for _ in range(n+1)]
dp[0][0] = 1

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

        if j + a[i-1] <= s:
            dp[i][j+a[i-1]] += dp[i-1][j]
            dp[i][j+a[i-1]] %= mod

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

Submission status: Accepted

Solution code:
import numpy as np
N,S=map(int,input().split())
As=list(map(int,input().split()))

MOD=998244353

#d = [[0]*3001 for _ in range(3001)]
d=np.zeros((3001,3001))
d[0,0]=1

for i in range(1,N+1):
    Ai=As[i-1]
    d[i] += 2*d[i-1]
    d[i,Ai:] += d[i-1][:-Ai]
    d[i] %= MOD
print(int(d[N][S]))