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:
## coding: UTF-8
mod = 998244353

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

dp = []
for i in range(N+1):
    #dp.append([0]*3010)
    dp.append([0]*(S+1))
#print(dp)

dp[0][0] = 1
#print(dp)

#print('dpstart')
for i in range(N):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= mod
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= mod        
        if(j >= A[i]):
            dp[i+1][j] += dp[i][j-A[i]]
            dp[i+1][j] %= mod
    #print(dp)

print(dp[N][S])

Submission status: Accepted

Solution code:
N,S=map(int,input().split())
A=list(map(int,input().split()))
pr=998244353
def gya(n):
    return pow(n,pr-2,pr)
p=pow(2,N-1,pr)
l=[0]*(S+1)
g=gya(2)
for i in A:
    for j in range(S-i,-1,-1):
        l[i+j]=(l[i+j]+(l[j]*g))%pr
    if i<=S:
        l[i]+=p
print(l[-1])

Submission status: Accepted

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

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


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

for i in range(n):
    if i == 0:
        dp[0][0] = 2
        if a[i] < s+1:
            dp[0][a[i]] = 1
        continue

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

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

Submission status: Accepted

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

mod = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
dp = [0] * (S+1)
dp[0] = pow(2, N, mod)
two_inv = pow(2, mod-2, mod)
for i, a in enumerate(A):
    for j in range(a, S+1)[::-1]:
        dp[j] = (dp[j] + dp[j-a] * two_inv) % mod
print(dp[S])

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 998244353; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, S = getlist()
	A = getlist()
	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] %= con
			w = A[i]
			if j + w <= S:
				DP[i + 1][j + w] += DP[i][j]
				DP[i + 1][j + w] %= con

	print(DP[-1][-1])


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, s = map(int, input().split())
    dp = [0] * (s + 1)
    dp[0] = 1
    res = 0
    A = list(map(int, input().split()))
    for a in A:
        ndp = [2 * t % MOD for t in dp]
        if s >= a:
            for i in range(s - a, -1, -1):
                ndp[i + a] += dp[i]
                ndp[i + a] %= MOD
        dp = ndp


    print(dp[s] % MOD)
resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

dp = [0]*(S+1)
dp[0] = 1
for a in A:
    ndp = [0]*(S+1)
    for total,cnt in enumerate(dp):
        ndp[total] += dp[total]*2
        ndp[total] %= MOD
        if total+a <= S:
            ndp[total+a] += dp[total]
            ndp[total+a] %= MOD
    dp = ndp

print(dp[-1]%MOD)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)

MOD = 998244353  # type: int
INV = pow(2, MOD - 2, MOD)

def calc_fraction_mod(numerator):
    '''
        returns numerator / denominator (mod MOD)
    '''
    #inv = pow(denominator, MOD - 2, MOD)
    return numerator * INV % MOD


def solve(N: int, S: int, A: "List[int]"):
    A.sort()
    dp = [0] * (S + 1)
    dp[0] = pow(2, N, MOD)
    for i, a in enumerate(A):
        for s in range(S + 1)[::-1]:
            if dp[s] == 0:
                continue
            if s + a <= S:
                dp[s + a] += calc_fraction_mod(dp[s])
                dp[s + a] %= MOD
    print(dp[S])

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, S, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp = [[0 for i in range(s+1)] for j in range(n+1)]
mod = 998244353

dp[0][0] = 1
for i in range(n):
    for summ in range(s+1):
        if summ - nums[i] >= 0:
            dp[i+1][summ] = (2 * dp[i][summ] + dp[i][summ - nums[i]]) % mod
        else:
            dp[i+1][summ] = (2 * dp[i][summ]) % mod


# print(dp)
print(dp[n][s] % mod)

Submission status: Accepted

Solution code:
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n,s=NM()
l=[0]+L()
dp=[[0]*(s+1) for i in range(n+1)]
dp[0][0]=1
ans=0
mod=998244353
inv2=pow(2,mod-2,mod)
pow2n=pow(2,n,mod)
for i in range(1,n+1):
    x=l[i]
    for j in range(s+1):
        dp[i][j]=dp[i-1][j]
    for j in range(x,s+1):
        dp[i][j]+=dp[i-1][j-x]*inv2
        dp[i][j]%=mod
ans=dp[-1][-1]*pow(2,n,mod)%mod
print(ans)

Submission status: Accepted

Solution code:
def inv_mod(a, p=10**9+7):
    p = abs(p)
    a %= p
    stack = []
    p0 = p
    while a > 1:
        d, a, p = p//a, p%a, a
        stack.append(d)
    x, y = 1, 0
    while stack:
        d = stack.pop()
        x, y = y-d*x, x
    return x % p0

MOD = 998244353
inpl = lambda: list(map(int,input().split()))
N, S = inpl()
A = inpl()
F = [[0]*(S+1) for _ in range(N+1)]
F[0][0] = pow(2,N,MOD)
p = inv_mod(2,MOD)

for k in range(1,N+1):
    for s in range(S+1):
        if F[k-1][s] > 0:
            F[k][s] += F[k-1][s]
            F[k][s] %= MOD
            t = s + A[k-1]
            if t <= S:
                F[k][t] += F[k-1][s] * p
                F[k][t] %= MOD
print(F[N][S])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul
from decimal import Decimal

mod = 998244353
INF = 10 ** 13
sys.setrecursionlimit(2147483647)
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


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


print(dp[s])

Submission status: Accepted

Solution code:
#解説ツイート
#A
#掛け算を普通にするだけです

#B
#いやらしい引掛けポイントがあります
#オーバーフロー対策のために途中で10^18を超えたら-1を出力する、と行きたいところですが、
#その後に0が出てきたら終わりです。
#対処法としてはソートしてから順番に掛けて、途中で10^18を超えたら-1を出力するという方針で行けばOKです。
#ソートすることによって、(A_1*...*A_k)≦(A_1*...A_{k+1})が成り立つようになります。

#C
#いやらしい問題その2です。
#浮動小数点数をそのまま扱うと誤差が出てくるのでペナルティが生えます
#よってBをinputする際に、"."でsplitすることによって整数として扱うことができます。
#その後は整数として計算すればOKです。そのために1.1を1.10というような表記をすることになっています。

#D
#まずは素因数分解します。
#素数pについてe=ord_p(N)に対して、
#e≧k*(k+1)/2となる最大のkを求めてpごとの総和を取ればOKです。

#E
#中央値の最小値と中央値の最大値を求めればOK
#それぞれの場合はX_i=A_iとすれば中央値最小になるしX_i=B_iとすれば中央値は最大となります。
#Nが偶数なら中央値は1/2刻み,Nが奇数なら中央値は1となるため、Nが偶数ならば全体を2倍して考えます。
#その後での最小値と最大値の間にある整数の数を出力すればOKです。X_iを適切に1ずらせば
#中央値の値の取らせ方はある程度の融通がききます。

#F
#dpです。python勢の人はpypyを使うことをおすすめします。以下のコードをpythonで提出したらTLEしました。
#dp[i][j]={1,...,i}の部分集合Uについて、Σ[x∈U]A_x=jとなるようなU全体の集合をP(j)としたときの
#Σ[U∈P(j)]2^(N-len(U)
#が答えとなり、結局dp[N][S]を出力すればよいです。jについてはSより大きいところは見る必要がないので
#計算量はO(NS)となります。

N,S=map(int,input().split())
A=[int(i) for i in input().split()]
mod=998244353
dp=[[0 for j in range(S+1)]for i in range(N+1)]
pow2N=pow(2,N,mod)
dp[0][0]=pow2N
inv2=pow(2,mod-2,mod)
for i in range(N):
    for j in range(S+1):
        if dp[i][j]!=0:
            dp[i+1][j]+=dp[i][j]
            dp[i+1][j]%=mod
            if j+A[i]<=S:
                dp[i+1][j+A[i]]+=(inv2*dp[i][j])%mod
                dp[i+1][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
ans=[[0 for e in range(S+1)] for f in range(N+1)]
ans[0][0]=1
for i in range(N):
 for k in range(S+1):
  ans[i+1][k]=ans[i][k]*2
  ans[i+1][k]%=mod
 for j in range(A[i],S+1):
  ans[i+1][j]+=ans[i][j-A[i]]
  ans[i+1][j]%=mod
print(ans[N][S])

Submission status: Accepted

Solution code:
def main():
    mod=998244353
    n,s=map(int,input().split())
    A=list(map(int,input().split()))
    DP=[[0]*(s+1) for _ in range(n+1)]
    p=1
    for i in range(n+1):
        DP[i][0]=p
        p*=2
        p%=mod
    for i,a in enumerate(A):
        for j in range(1,s+1):
            DP[i+1][j]=DP[i][j]*2
            if j>=a:
                DP[i+1][j]+=DP[i][j-a]
            DP[i+1][j]%=mod
    print(DP[-1][-1])
    #print(DP)
    
if __name__=='__main__':
    main()

Submission status: Accepted

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

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

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

beki2 = [1]
MOD = 998244353
for i in range(4000):
    beki2.append(beki2[-1]*2%MOD)

for i in range(n):
    ai = a[i]
    if(ai<=s):
        dp[i+1][ai] += beki2[i]
    for j in range(s+1):
        valj = dp[i][j]
        dp[i+1][j] += (valj * 2)
        wa = j + ai
        if(wa <= s):
            dp[i+1][wa] += valj
    for j in range(s+1):
        dp[i+1][j] %= MOD

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys

N,S, *A = map(int, sys.stdin.buffer.read().split())
mod = 998244353

answer = [0 for _ in range(S+1)]
power2 = 1

for a in A:
  answer_next = [(2*b)%mod for b in answer]
  if a<=S:
    answer_next[a] = (answer_next[a]+power2)%mod
    for i in range(a+1,S+1):
      answer_next[i] = (answer_next[i]+answer[i-a])%mod
  answer = answer_next
  power2 = (2*power2)%mod

print(answer[S])

Submission status: Accepted

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

al = list(map(int,input().split()))

ans = 0
dp = [0 for _ in range(s + 1)]
dp[0] = 1
for i in range(n):
    for k in range(s, -1, -1):
        if k - al[i] < 0:
            dp[k] = 2 * dp[k]
        else:
            dp[k] = 2 * dp[k] + dp[k-al[i]]
        dp[k] %= 998244353

print(dp[-1])

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)]
dp[0][0]=2
if a[0]<=s: dp[0][a[0]]=1

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

Submission status: Accepted

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

div = pow(2, MOD-2, MOD)

DP = [0] * (S+1)
DP[0] = pow(2, N, MOD)
for a in A:
	for i in range(S-a, -1, -1):
		if DP[i] == 0: continue
		DP[i+a] = (DP[i+a] + DP[i] * div) % MOD

print(DP[S])

Submission status: Accepted

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

Submission status: Accepted

Solution code:

mod = 998244353

def modinv(x, m = mod):
    b = m
    u = 1
    v = 0
    while b:
        t = x // b
        x -= t * b
        x, b = b, x
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u

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

    pow2 = [0 for _ in range(n+1)]
    pow2[0] = 1
    for i in range(n):
        pow2[i+1] = (pow2[i] * 2) % mod

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

    print(dp[s])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N, S = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
MOD = 998244353

for i in range(N):
    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]%MOD)

Submission status: Accepted

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

print(dp[N][S])

Submission status: Accepted

Solution code:
import numpy as np

MOD = 998244353

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

dp = np.zeros((N+1, S+1), np.int64)
dp[0][0] = 1
for n, A in enumerate(As):
    dp[n+1, :] = dp[n, :] * 2
    dp[n+1, A:] += dp[n, :-A]
    dp[n+1] %= 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)]
dp[0][0] = 1
for i in range(N):
    dp.append([d * 2 % MOD for d in dp[-1]])
    for k in range(A[i], S + 1):
        dp[-1][k] += dp[-2][k - A[i]]

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

Submission status: Accepted

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

two_inv = pow(2, MOD - 2, MOD)

# dp[i][j] = i番目まで見て和がjとなるような場合の数
dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = pow(2, n, MOD)
for i, ai in enumerate(a):
    for j in range(s + 1):
        if j - ai >= 0:
            dp[i + 1][j] = (dp[i][j] + dp[i][j - ai] * two_inv) % MOD
        else:
            dp[i + 1][j] = dp[i][j]

# print(*dp, sep='\n')
print(dp[n][s])
# # dp[i][j] = i個使って和がjとなるような場合の数
# dp = [[defaultdict(int)] * (s + 1) for _ in range(n + 1)]
# dp[0][0][0] = 1
# for ai in a:
#     dp[1][ai] += 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
# dp[i][j] = iこめまで見てS=jのときのans
for i,a in enumerate(A):
    for j in range(s+1):
        dp[i+1][j] += dp[i][j]*2%mod
        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[n][s]%mod)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

dp = [0]*(S+1)
dp[0] = 1
for a in A:
    ndp = [0]*(S+1)
    for total,cnt in enumerate(dp):
        ndp[total] += (dp[total]*2)%MOD
        if total+a <= S:
            ndp[total+a] += dp[total]
            ndp[total+a] %= MOD
    dp = ndp

print(dp[-1]%MOD)

Submission status: Accepted

Solution code:
import os

import itertools
import sys

# import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353

N, S = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))


def test(N, S, A):
    A = np.array(A)
    ret = 0
    for choices in itertools.product([True, False], repeat=N):
        choices = np.array(choices, dtype=bool)
        if A[choices].sum() == S:
            ret += 2 ** (N - choices.sum())
    print(ret)


# test(N, S, A)

# # dp[i][s]: i まで見て和が s である数 / 2^(使った数)
# dp = [[0] * (S + 1) for _ in range(N + 1)]
# dp[0][0] = 1
# for i, a in enumerate(A):
#     dp[i + 1] = list(dp[i])
#     for s in reversed(range(S - a + 1)):
#         dp[i + 1][s + a] += dp[i][s] / 2
# print(dp[-1][S] * (2 ** N))


div2 = pow(2, MOD - 2, MOD)
# dp[s]: i まで見て和が s である数 / 2^(使った数)
dp = [0] * (S + 1)
dp[0] = 1
for i, a in enumerate(A):
    for s in reversed(range(S - a + 1)):
        dp[s + a] += dp[s] * div2
        dp[s + a] %= MOD
print(dp[S] * pow(2, N, MOD) % MOD)

Submission status: Accepted

Solution code:
import numpy as np
import numba
@numba.njit("void(i8,i8,i8[:])", cache=True)
def solve(N,S,A):
    dp = np.zeros((N+1, S+1), dtype=np.int64)#[[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])

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 998244353
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from copy import copy

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

    # iである個数
    dp = [[0] * (s + 1) for _ in range(n)]
    dp[0][0] = 2
    if a[0] <= s:
        dp[0][a[0]] = 1

    for i, x in enumerate(a[1:], 1):
        dp[i] = [y * 2 % MOD for y in dp[i - 1]]
        for j in range(s + 1):
            cur = j + x
            if cur > s:
                break
            dp[i][cur] += dp[i - 1][j]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

dp = dpinit((N+1,S+1))

dp[0][0] = 1
for i in range(N):
    a = A[i]
    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[N][S]%MOD)

Submission status: Accepted

Solution code:
K = 96
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
P = 998244353
pa = (1 << 64) - ((1 << 64) % P)
m = int(("1" * 32 + "0" * 64) * 3030, 2)
modP = lambda x: x - ((x & m) >> 64) * pa
s = 1 << K * S
for a in A:
    s = 2 * s + (s >> K * a)
    s = modP(s)
print((s & ((1 << K) - 1)) % P)

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 998244353

def solve():
    n,s = LI()
    a = LI()
    dp = [0]*(s+1)
    dp[0] = pow(2,n,mod)
    inv = pow(2,mod-2,mod)
    for i in a:
        for k in range(s)[::-1]:
            nk = k+i
            if nk > s:
                continue
            dp[nk] += dp[k]*inv%mod
            dp[nk] %= mod
    print(dp[s])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, S = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353
#print(a)
dp = [0] * (S + 1)
dp[0] = 1
md = pow(2, mod - 2, mod)
for i in range(N):
  for x in range(S, -1, -1):
    if dp[x] == 0: continue
    if x + a[i] <= S:
      dp[x + a[i]] += dp[x] * md % mod
      dp[x + a[i]] %= mod
print(dp[-1] * pow(2, N, mod) % mod)

Submission status: Accepted

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = inf ;ans = 0 ;count = 0 ;pro = 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 si in range(s+1):
    dp[i+1][si] += dp[i][si]*2
    dp[i+1][si] %= mod
    if not 0 <= si+A[i] < s+1:continue
    dp[i+1][si+A[i]] += dp[i][si]
    dp[i+1][si+A[i]] %= mod
# print(*dp,sep = "\n")
print(dp[n][s])

Submission status: Accepted

Solution code:

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

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

mod = 998244353

dp = [0] * (S+1)
dp[0] = pow(2,N,mod)

half = 499122177

for i in range(N):

    for j in range(S,-1,-1):

        if j + A[i] <= S:
            dp[j+A[i]] += dp[j] * half
            dp[j+A[i]] %= mod

print (dp[-1] % mod)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

M =998244353

n, s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0]* (s+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = pow(2,i,M)
for i in range(1,n+1):
    for j in range(1,s+1):
        dp[i][j] = dp[i-1][j]*2
        if j>=a[i-1]:
             dp[i][j] += dp[i-1][j-a[i-1]]
        dp[i][j] %= M
print(dp[n][s])

Submission status: Accepted

Solution code:
import sys
import numpy as np

n, s, *aaa = map(int, sys.stdin.buffer.read().split())
MOD = 998244353

dp = np.zeros(s + 1, np.int64)
dp[0] = 1

for a in aaa:
    ndp = dp * 2 % MOD
    if a <= s:
        ndp[a:] += dp[:-a]
    dp = ndp % MOD

print(dp[s])

Submission status: Accepted

Solution code:
mod=998244353

n,s=map(int,input().split())
A=list(map(int,input().split()))
div2=pow(2,mod-2,mod)
dp=[0]*(s+1)
dp[0]=pow(2,n,mod)

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

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

Submission status: Accepted

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

mod = 998244353

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

inv2 = pow(2, mod-2, mod)
dp = [[0]*(S+1) for _ in range(N+1)]

dp[0][0] = pow(2, N, mod)
for i, a in enumerate(A):
    dp[i+1] = dp[i][:]
    for s in range(S-a+1):
        dp[i+1][s+a] = (dp[i+1][s+a] + dp[i][s] * inv2) % mod

print(dp[N][S])

Submission status: Accepted

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

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 in range(n):
	for j in range(s+1):
		dp[i+1][j] = dp[i][j] * 2
		if j >= a[i]:
			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 = list(map(int,input().split()))
dp = [[0 for i in range(s+1)] for j in range(n+1)]
dp[0][0] = 1
mod = 998244353
for i in range(1,n+1):
  x = a[i-1]
  for j in range(s+1):
    dp[i][j] += dp[i-1][j]*2
    dp[i][j] %= mod
  for j in range(x,s+1):
    dp[i][j] += dp[i-1][j-x]
    dp[i][j] %= mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:
mod = 998244353
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

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

    half = pow(2, mod-2, mod)
    dp = [[0] * (S+1) for _ 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+1][j] + dp[i][j])%mod
            if j+a <= S:
                dp[i+1][j+a] = (dp[i+1][j+a] + (dp[i][j] * half)%mod)%mod
    print((dp[-1][S] * pow(2, N, mod))%mod)


if __name__ == '__main__':
    main()

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

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

Submission status: Accepted

Solution code:
N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
inv=pow(2,mod-2,mod)

poly=[0 for i in range(3001)]
poly[0]=1
for i in range(N):
    for j in range(3000,-1,-1):
        if j>=A[i]:
            poly[j]=inv*poly[j-A[i]]+poly[j]
            poly[j]%=mod

res=pow(2,N,mod)*poly[S]
res%=mod
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,s,*a = map(int,read().split())

MOD = 998244353
def mul(c,m,dp): #multiply (2+x^c) up to x^m
    for i in range(m,c-1,-1):
        dp[i] *= 2
        dp[i] += dp[i-c]
        dp[i] %= MOD
    for i in range(min(m,c-1),-1,-1):
        dp[i] *= 2
        dp[i] %= MOD

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

for i in a:
    mul(i,s,dp)

print(dp[-1]%MOD)
#print(dp)

Submission status: Accepted

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