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:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# 集合[a1, a2...an]内で以下２つの条件を満たす部分集合の組(T, U)はいくつあるか問題
# 1: U ⊆ Tである
# 2: Uがある条件を満たす

# Tの中にUがいくつか含まれる
# ①iが進むごとにTの候補がn倍ずつ増えていく
# ②その後、Uを組むためのカウントを進める

''' ABC104 D - We Love ABC
S = '????C?????B??????A???????'
N = len(S)
# dp[i][j]: i番目にjまで丸をつけ終えている通り
dp = [[0] * 4 for _ in range(N + 1)]
dp[0][0] = 1

for i in range(N):
    # 通りの数を増やす
    for j in range(4):
        if S[i] != '?':
            dp[i + 1][j] += dp[i][j]
            dp[i + 1][j] %= mod
        else:
            dp[i + 1][j] += 3 * dp[i][j]
            dp[i + 1][j] %= mod
    # カウントが進むものを加える
    if S[i] == 'A' or S[i] == '?':
        dp[i + 1][1] += dp[i][0]
        dp[i + 1][1] %= mod
    if S[i] == 'B' or S[i] == '?':
        dp[i + 1][2] += dp[i][1]
        dp[i + 1][2] %= mod
    if S[i] == 'C' or S[i] == '?':
        dp[i + 1][3] += dp[i][2]
        dp[i + 1][3] %= mod
print(dp[N][3] % mod)
'''

# ABC169 F - Knapsack for All Subsets
N, S = getNM()
A = getList()
MOD = 998244353

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

for i in range(N):
    # 通りの数を増やす
    for j in range(S + 1):
        dp[i + 1][j] += dp[i][j] * 2
        dp[i + 1][j] %= MOD
    # カウントが進むものを加える
    for j in range(S + 1):
        if j - A[i] >= 0:
            dp[i + 1][j] += dp[i][j - A[i]]
            dp[i + 1][j] %= MOD
print(dp[N][S] % MOD)

Submission status: Accepted

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20

class Polynomial:
    def __init__(self,dim=0,const=1):
        self.values = [(dim,const)]
    def __add__(self,other):
        return self.values + other.values


class PolySolver:
    def __init__(self,size):
        self.size = size
        self.f = np.zeros(size, np.int64)
        self.f[0] = 1


    def multiple(self,polynomial,MOD): # const1 * x^dim1 + const2 * x^dim2 + ... をfにかけ合わせる
        new_F = np.zeros(self.size, np.int64)
        for dim,const in polynomial:
            if dim != 0:
                g = np.zeros(self.size, np.int64)
                g[dim:] += self.f[:-dim]
            else:
                g = const * self.f.copy()
            new_F += g

        self.f = new_F
        self.f %= MOD

    
    def get_coefficient(self,dim):
        return self.f[dim]
    
def main():
    N,S=mi()
    A=list(mi())
    MOD = 998244353

    poly = PolySolver(3010)
    for a in A:
        f = Polynomial(const=2) + Polynomial(dim=a)
        poly.multiple(f,MOD)

    print(poly.get_coefficient(S))



if __name__ == "__main__":
    main()

Submission status: Accepted

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

mod = 998244353

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

#print(dp)
print(dp[N-1][S])

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
# mod = 10**9+7
mod = 998244353

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

dp = [[0 for j in range(S+1)] for i in range(N+1)]
dp[0][0] = 1

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, S = getNM()
A = getList()
MOD = 998244353

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

# [3 1 ④] 1 5 [⑨ ② 6] 5 [3]みたいな感じで数えあげる
for i in range(N):
    for j in range(S + 1):
        # Tに含める通りと含めない通り
        dp[i + 1][j] += dp[i][j] * 2
        dp[i + 1][j] %= MOD
        if j - A[i] >= 0:
            # Tに含める通りかつUに含める通り
            dp[i + 1][j] += dp[i][j - A[i]]
            dp[i + 1][j] %= MOD
print(dp[N][S] % MOD)

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, v in enumerate(a):
        dp[i+1] += dp[i]*2
        if v <= s:
            dp[i+1][v:] += dp[i][:-v]
        dp[i+1] %= MOD
    print(int(dp[n][s])%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 解説AC
# Tの部分集合をUとすると
# A[i]番目の項目について、
# (1)Tに選ばれない
# (2)Uに選ばれない
# (3)Uに選ばれる
# の3通りの遷移がある
# (1)(2)の場合も含めて数え上げていく（その場合、和は変わらない）

import sys
readline = sys.stdin.readline

N,S = map(int, readline().split())
A = list(map(int,readline().split()))
DIV = 998244353

# dp[i][j] = i番目の数まで見たときにjになっている場合の数
dp = [[0] * (S + 1) for i in range(N + 1)]
dp[0][0] = 1
for i in range(len(A)):
  for j in range(S + 1):
    if dp[i][j] == 0:
      continue
    dp[i + 1][j] += dp[i][j] * 2
    dp[i + 1][j] %= DIV
    if j + A[i] <= S:
      dp[i + 1][j + A[i]] += dp[i][j]
      dp[i + 1][j + A[i]] %= DIV
      
print(dp[-1][-1])

Submission status: Accepted

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

dp = [[0]*(K+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    x = X[i]
    for j in range(K+1):
        dp[i+1][j] = 2*dp[i][j]
        if j-x>=0:
            dp[i+1][j] += dp[i][j-x]
        dp[i+1][j] %= MOD
print(dp[-1][-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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 = map(int, readline().split())
A = list(map(int,readline().split()))

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

Submission status: Accepted

Solution code:
def main():
    MOD = 998244353
    N, S = list(map(int, input().split()))
    A = list(map(int, input().split()))
    dp = [[0] * (S + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i, a in enumerate(A):
        n = i + 1
        for s in range(S + 1):
            dp[n][s] += 2 * dp[n - 1][s]
            if s - a >= 0:
                dp[n][s] += dp[n - 1][s - a]
            dp[n][s] %= MOD
    print(dp[N][S])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

# import bisect
# import numpy as np
from collections import deque
# map(int, sys.stdin.read().split())



def input():
    return sys.stdin.readline().rstrip()


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



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

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

# for r in range(N):
#     for s in range(S+1):
#         b[r+1][s] += b[r][s]
#         if s-A[r]>=0:
#             b[r+1][s] += b[r][s-A[r]]
#         if s==A[r] or s==0:
#             b[r+1][s] += 1
#         b[r+1][s] %= MOD

# ans = 0
# for i in range(N):  
#     ans += b[i+1][S]
#     ans %= MOD
    
# print(ans)

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

print(dp[N][S])

Submission status: Accepted

Solution code:
N,S = map(int,input().split())
A = 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: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
N, S = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
mod = 998244353
coef = np.zeros(3001, dtype=int)
coef[0] = 1
for a in A:
    coef2 = coef[:-a].copy()
    coef *= 2
    coef[a:] += coef2
    coef %= mod
print(coef[S])

Submission status: Accepted

Solution code:
import numpy as np
N, S = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
dp = np.array([0] * (3001), dtype=int)
dp[0] = 2
dp[A[0]] = 1
mod = 998244353
for a in A[1:]:
    dpn = np.zeros(3001, dtype=int)
    dpn[a:] = dp[:-a]
    dpn += dp * 2
    dpn %= mod
    dp = dpn
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):
        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 numpy as np
N, S = map(int, input().split())
A = np.array(list(map(int, input().split())))
P = 998244353
table = np.zeros((N, S+1), dtype=int)
table[0, 0] = 2
if A[0] <= S:
  table[0, A[0]] = 1
for i in range(1, N):
  Ai = A[i]
  table[i] += 2*table[i-1]
  if Ai <= S:
    table[i][Ai:] += table[i-1][:S-Ai+1]
  table[i] = table[i]%P
print(table[N-1][S])

Submission status: Accepted

Solution code:
import numpy as np

N, S = map(int, input().split())
A = np.array(list(map(int, input().split())))
P = 998244353
table = np.zeros((N, S+1), dtype=int)
table[0, 0] = 2
if A[0] <= S:
    table[0, A[0]] = 1
for i in range(1, N):
    Ai = A[i]
    table[i] += 2*table[i-1]
    if Ai <= S:
        table[i][Ai:] += table[i-1][:S-Ai+1]
    table[i] = table[i]%P

print(table[N-1][S])

Submission status: Accepted

Solution code:
import sys
import bisect
import math
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: Accepted

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

M, MOD = 3005, 998244353

dp = [[0 for i in range(M)] for j in range(M)]
n, s = map(int, input().split())
a = list(map(int, input().split()))
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 s >= j + a[i]:
            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
import numpy as np
P = 998244353


def main(N, S, AS):
    DP = np.zeros((S + 1, N + 1), dtype=np.int64)
    DP[0, 0] = 1
    # print(DP)

    for i in range(N):
        for j in range(S + 1):
            v = DP[j, i] * 2
            if AS[i] <= j:
                v += DP[j - AS[i], i]
            DP[j, i + 1] = v % P

    # print(DP)
    print(DP[S, N])


if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'void(i8,i8,i8[:])')(main)
    # b1: bool, i4: int32, i8: int64, double: f8, [:], [:, :]
    cc.compile()
    exit()
else:
    # read parameter
    N, S = map(int, input().split())
    AS = np.array(list(map(int, input().split())))
    from my_module import main
    main(N, S, AS)

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

dp = [[0 for 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 % mod
        if a[i] <= j:
            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[n][s]
#nこめまで選んだ時の和がｓの組

dp=[[0]*(s+1) for _ in range(n)]
a.sort()
#for i in range(s+1):
#    dp[0][i]=2
if a[0]>s:
    print(0)
    exit()

mod=998244353
 

dp[0][0]=2
dp[0][a[0]]+=1

for i in range(1,n):
    for j in range(s+1):
        #i番目を入れて選択するパターン
        dp[i][j]=dp[i-1][j]*2%mod
        if j>=a[i]:
            dp[i][j]+=dp[i-1][j-a[i]]%mod

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
n,s = map(int,input().split())
a = list(map(int,input().split()))
dp = np.zeros(s+1, dtype=np.int64)
"""
dp[i][j] := i番目までを選んで、和がちょうどjのときの場合の数
遷移 → 1増えると全体集合に選ぶ, Aには選ばない, Aに選ぶの3種類.
"""
mod = 998244353
dp[0] = 1
for i in range(n):
	p = (dp * 2) % mod
	p[a[i]:] += dp[:-a[i]]
	dp = p % mod
print(dp[s])

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    import numpy as np

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

    MOD = 998244353

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

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

    print(dp[S])

main()

Submission status: Accepted

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]*(3010)
	li=np.array(li)
	li[0]=1
	#print(li)

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



if __name__ == "__main__":
	main()

Submission status: Accepted

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

mod = 998244353

a = 1
arr2 = [1]
ans = 0
for i in range(N):
    a = a * 2 % mod
    arr2.append(a)

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

for i, a in enumerate(A_array):
    # print(dp)
    if S - a >= 0:
        ans = (ans + dp[S - a] * arr2[N - 1 - i]) % mod
    for j in range(S, -1, -1):
        dp[j] = (2 * dp[j] + (dp[j - a] if (j - a) >= 0 else 0)) % mod
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
MOD = 998244353

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

for i in range(N):
    tmp = coefs[:]
    coefs = coefs*2
    coefs[A[i]:] += tmp[:-A[i]]
    coefs%=MOD
    
print(coefs[-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 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
        if A[i] <= j:
            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()))
d=[[0]*(s+1) for _ in range(n+1)]
d[0][0]=1
for j in range(0,s+1):
    for i in range(1,n+1):
        d[i][j]=2*d[i-1][j]
        if a[i-1]<=j:
            d[i][j]+=d[i-1][j-a[i-1]]
        d[i][j]=d[i][j]%998244353
print(d[n][s])

Submission status: Accepted

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


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

    MOD = 998244353

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

    for i in range(n):
        p = (dp * 2) % MOD
        p %= MOD
        p[A[i]:] += dp[:-A[i]]
        dp = p % MOD

    print(dp[s])


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    n, s = map(int, input().split())
    A = np.array([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: Accepted

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: Accepted

Solution code:
n, s = map(int, input().split())
a = list(map(int, input().split()))
import numpy as np
mod = 998244353
f = np.zeros(3020, np.int64)
f[0] = 1
for b in a:
  ff = 2*f
  ff[b:] += f[:-b]
  ff %= mod
  f = ff
print(f[s])

Submission status: Accepted

Solution code:
N, S = map(int, input().split())
A = [int(i) for i in input().split()]

mod = 998244353

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

Submission status: Accepted

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 %= p
    continue
  tmp = 2*dp
  dp = np.append(np.zeros(a),dp[:S-a+1])
  dp += tmp
  dp %= p
print(int(dp[S]))

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
#import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect

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

dp=[[0]*3001 for _ in range(n+1)]
dp[0][0]=1
res={i for i in range(1,n+1)}
for i in range(1,n+1):
    for j in range(3001):
        if j>=a[i-1] and dp[i-1][j-a[i-1]]!=0:
            dp[i][j]=(2*dp[i-1][j]+dp[i-1][j-a[i-1]])%mod
           
        else:
            dp[i][j]=(2*dp[i-1][j])%mod
ans=0
print(dp[n][s])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
mod = 998244353
n, s = map(int, input().split())
a = [int(x) for x in input().split()]
dp = [[0]*(s + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
    for j in range(s + 1):
        dp[i][j] += dp[i - 1][j]*2
        dp[i][j] %= mod
        if j - a[i - 1] >= 0:
            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

def solve():
    MOD = 998244353
    inv2 = pow(2, MOD-2, MOD)

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

    dp = [0] * (S+1)
    dp[0] = pow(2, N, MOD)
    for A in As:
        for k in reversed(range(S-A+1)):
            dp[k+A] += dp[k] * inv2
            dp[k+A] %= MOD

    print(dp[-1])


solve()

Submission status: Accepted

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


def main():
    N, S = map(int, input().split())
    *A, = map(int, input().split())
    dp = [[0]*(3001) for _ in range(N+1)]
    MOD = 998244353
    m = pow(2, MOD-2, MOD)
    dp[0][0] = pow(2, N, MOD)
    for i in range(1, N+1):    
        for j in range(3001):
            dp[i][j] += dp[i-1][j]
            if j-A[i-1]>=0:
                dp[i][j] += dp[i-1][j-A[i-1]]*m
            dp[i][j] %= MOD

    print(dp[N][S])


main()

Submission status: Accepted

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

mod = 998244353


dp = np.zeros(S+1)

dp[0] = 1

for i in range(N):
    tmp = dp*2
    tmp[a[i]:] += dp[:-a[i]]
    dp = tmp % mod

print(int(dp[S]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 998244353

n, s = map(int, input().split())
a = [int(item) for item in input().split()]

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

for i, item in enumerate(a):
    for j in range(s, -1, -1):
        if dp[i][j] == 0:
            continue
        if j + item <= s:
            dp[i+1][j+item] += dp[i][j] 
        dp[i+1][j] += dp[i][j] * 2
        dp[i+1][j] %= MOD

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

Submission status: Accepted

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

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

print(dp[N][S])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    N,S=pin()
    A=tupin()#調子にのるな
    mod=998244353
    
    #形式的冪級数を考える
    #普通の部分和ッ->集合内の各アイテムについて、選ぶか選ばないか。O(2^n)の探索
    #これを形式的冪級数でいえば、（1+x^a）を掛ける計算になる　指数時間ではない
    #つまり、集合A,Sに対して、[x^s]PI(1+x^a_i) (f_i)

    #次に、Aの部分集合について考える
    #サンプル1の場合、N==3なので8個の部分集合がある
    #つまり、F3＝1+(f_1+f_2+f_3)+(f1_f2+f2_f3+f3_f1)+f1_f2_f3を考える
    #果たして、一般的なNにたいして多項式時間でにFnをもとめれば指数時間は完全回避できる
    #F3=(1+f1+f2+f1f2)+f3{(1+f1+f2+f1f2)}
    #  =(1+f3)(1+f1+f2+f1f2)
    #  =(f3で追加された新しいところ)(N=2のときのすべての部分集合)

    #これは、f3をSの部分集合にふくめるか、含めないかの探索と同等
    #一般的にFn=F_n-1*(1+fn)=PI(1+fn)とわかる

    #求めるものは[x^S]PI(1+fn)=[x^S]PI(2+x^a)

    from collections import defaultdict #本当は良くないがわかりやすさのためココに置く
    from copy import deepcopy
    
    ans=defaultdict(int)#i
    ans[0]=1 #init ,1=x^0より
    #print(ans)
    for a in A:
        #ans そのものと、ansの係数にx^aをかけたものを足し算    
        temp=defaultdict(int)
        for x in ans:
            if x+a<=S:
                temp[x+a]=ans[x]
            
            ans[x]*=2
            ans[x]%=mod
        for t in temp:
            if t<=S:
                ans[t]+=temp[t]
                ans[t]%=mod
    print(ans[S])    
    
#%%submit!
resolve()

Submission status: Accepted

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

#print(A)

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

DP[0][0]=1

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

Submission status: Accepted

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: Accepted

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

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

Submission status: Accepted

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

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

for i in range(1,N+1):
  for k in range(S+1):
    dp[i][k]=2*dp[i-1][k]
    if k-alist[i-1]>=0:
      dp[i][k]+=dp[i-1][k-alist[i-1]]
    dp[i][k]%=MOD
#print(dp[-1])

print(dp[N][S])