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: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
from numba import njit, i4


@njit(i4(i4, i4, i4[:]), cache=True)
def solve(N, S, A):
    MOD = 998244353
    dp = np.zeros((N + 1, S + 1), dtype=np.int32)
    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
    return dp[-1][-1]


N, S = map(int, input().split())
A = np.array(input().split(), dtype=np.int32)
print(solve(N, S, A))

Submission status: Wrong Answer

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

# Sのそれぞれの項目について
# (1)Tに属さない
# (2)Tに属すが計算に使われない
# (3)Tに属して計算に使われる
# の3通りがある

# dp[i][j] = i番目の数を処理したときに、合計がjになるものは何通りあるか

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

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

dp[0][0] = 1
for i in range(N):
  val = A[i]
  for j in range(len(dp[i]) - 1, -1, -1):
    if dp[i][j] == 0:
      continue
    dp[i + 1][j] += dp[i][j] * 2 # 使わない場合、選ばない場合
    if j + val <= S:
      dp[i + 1][j + val] += dp[i][j]
  
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [-1 for _ in range(S+1)]
visited = [0]
dp[0] = 1
dp = tuple(dp)
for k in range(N):
  a = A[k]
  nextdp = list(dp)
  nextvisit = []
  for item in visited:
    #process1 追加する
    if item + a <= S:
      if nextdp[item+a] == -1:
        nextvisit.append(item+a)
        nextdp[item+a] = 0
      nextdp[item+a] += dp[item]
      nextdp[item+a] %= mod
    #process2 追加しない
    nextdp[item] += dp[item]
    nextdp[item] %= mod
  dp = tuple(nextdp)
  visited.extend(nextvisit)

print(dp[-1])

Submission status: Wrong Answer

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [0 for _ in range(S+1)]
visited = [0]
dp[0] = 1
dp = tuple(dp)
for k in range(N):
  a = A[k]
  nextdp = list(dp)
  nextvisit = []
  for item in visited:
    #process1
    if item + a <= S:
      if nextdp[item+a] == 0:
        nextvisit.append(item+a)
      nextdp[item+a] += dp[item]
    #process2
    if item <= S:
      if nextdp[item] == 0:
        nextvisit.append(item+a)
      nextdp[item] += dp[item]
  dp = tuple(nextdp)
  visited.extend(nextvisit)

print(dp[-1])

Submission status: Wrong Answer

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
mod = 998244353
conunter = [[0] for _ in range(S+1)] #counter[num][numに必要な要素数] = numの組み合わせ数
visited = [0]
conunter[0] = [1]

for k in range(N):
  a = A[k]
  new_count = []
  new_visit = []
  for item in visited:
    if item +a > S:
      break
    if len(conunter[item+a]) == 1:
      new_visit.append(item+a)
    new_count.append((item + a, tuple(conunter[item])))
  visited.extend(new_visit)
  for new in new_count:
    for k in range(len(new[1])):
      plus = new[1][k]
      if len(conunter[new[0]]) < k+2:
        conunter[new[0]].append(plus)
      else:
        conunter[new[0]][k+1] += plus


two = [1]
for k in range(N):
  two.append(two[-1]*2%mod)


foo = conunter[-1]
ans = 0
for k in range(1, len(foo)): 
  ans = (ans + foo[k]*two[N-k])%mod
print(ans)

Submission status: Wrong Answer

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

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]

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

Submission status: Wrong Answer

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
        if j - A[i] >= 0:
            # Tに含める通りかつUに含める通り
            dp[i + 1][j] += dp[i][j - A[i]]
print(dp[N][S])

Submission status: Wrong Answer

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
    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: Wrong Answer

Solution code:
N, S=list(map(int,input().split()))
A=list(map(int,input().split()))
A=[0]+A
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 j in range(S+1):
        dp[i][j]+=2*dp[i-1][j] %998244353 # x[i]を入れないが、大きい方に入れるか入れないかが二通り
        if j+A[i]<=S:
            dp[i][j+A[i]]+=dp[i-1][j] %998244353#x[i]を入れる
print(dp[N][S])

Submission status: Wrong Answer

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
    d[i+1,A[i]:]=(d[i+1,A[i]:]+d[i,:-A[i]])%m
print(d[-1,-1]%m)

Submission status: Wrong Answer

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
    d[i+1,A[i]:]=(d[i+1,A[i]:]+d[i,:-A[i]])%m
print(d[-1,-1])

Submission status: Wrong Answer

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

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

# Add dummy data at first position
A_list = [None] + list(map(int, input().rstrip().split()))
#-----

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

for i in range(N):
    for j in range(S+1):
        if (j - A_list[i+1]) >=0:
            dp[i+1][j] = 2*dp[i][j] + dp[i][j - A_list[i+1]]
        else:
            dp[i+1][j] = 2*dp[i][j]

print(dp[N][S])

Submission status: Wrong Answer

Solution code:
import numpy as np

N, S = map(int, input().split())
A = np.array(list(map(int, input().split())))
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]

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

Submission status: Wrong Answer

Solution code:
import numpy as np

N, S = map(int, input().split())
A = np.array(list(map(int, input().split())))
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]

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

Submission status: Wrong Answer

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
table = [[0 for _ in range(S+1)] for _ in range(N)]
table[0][0] = 2
if A[0]<=S:
    table[0][A[0]] = 1
for i in range(1, N):
    Ai = A[i]
    for j in range(S+1):
        table[i][j] += 2*table[i-1][j]
        if j+Ai<=S:
            table[i][j+Ai] += table[i-1][j]

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

Submission status: Wrong Answer

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
table = [[0 for _ in range(S+1)] for _ in range(N)]
table[0][0] = 2
if A[0]<S:
    table[0][A[0]] = 1
for i in range(1, N):
    Ai = A[i]
    for j in range(S+1):
        table[i][j] += 2*table[i-1][j]
        if j+Ai<=S:
            table[i][j+Ai] += table[i-1][j]

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

Submission status: Wrong Answer

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

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

for i in range(n):
    for j in range(s + 1):
        if a[i] <= j:
            if len(dp[i][j - a[i]]) > 0:
                dp[i + 1][j] = [x + 1 for x in dp[i][j - a[i]]] + dp[i][j]
        else:
            dp[i + 1][j] = dp[i][j]

ans = 0


def power_func(a,n,p):
    bi = str(format(n,"b"))#2進表現に
    res = 1
    for i in range(len(bi)):
        res = (res*res) %p
        if bi[i] == "1":
            res = (res*a) %p
    return res


for i in dp[n][s]:
    ans += power_func(2, n - i, 998244353)
    ans %= 998244353
print(ans)

Submission status: Wrong Answer

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

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

for i in range(n):
    for j in range(s + 1):
        if a[i] <= j:
            if len(dp[i][j - a[i]]) > 0:
                dp[i + 1][j] = [x + 1 for x in dp[i][j - a[i]]] + dp[i][j]
        else:
            dp[i + 1][j] = dp[i][j]

ans = 0
for i in dp[n][s]:
    ans += 2 ** (n - i)
    ans %= 998244353
print(ans)

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

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]]
print(d[n][s])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N,S=map(int,input().split())
A=list(map(int,input().split()))

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

dp[0][0]=1

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


print(dp[N][S])

Submission status: Wrong Answer

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


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

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

    for i in a:
        p = [0] * (s + 1)
        dp, p = p, dp
        for j in range(s + 1):
            dp[j] += p[j] * 2
            if j + i <= s:
                dp[j + i] += p[j]

    print(dp[s])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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

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

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

    print(dp[s])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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)]
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] + dp[i-1][j-a[i]]
    else:
      dp[i][j] = dp[i-1][j]
    if j == a[i]:
      dp[i][j] += 1

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

Submission status: Wrong Answer

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

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

print(dp[N][S])

Submission status: Wrong Answer

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()#調子にのるな

    
    #形式的冪級数を考える
    #普通の部分和ッ->集合内の各アイテムについて、選ぶか選ばないか。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:
            temp[x+a]=ans[x]
            ans[x]*=2
        for t in temp:
            ans[t]+=temp[t]
    print(ans[S])    
        
    
    
#%%submit!
resolve()

Submission status: Wrong Answer

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

    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]
            if j + nexta > s:
                continue
            else:
                dp[i][j+nexta] += dp[i-1][j]
    print(dp[n][s])

resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    n, s = map(int, input().split())
    a = list(map(int,input().split()))
    dp = [[0]*(s+1) for _ in range(n+1)]
    dp[0][0] = 1

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

resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)


def main(input, print):
    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] <= s:
                dp[i+1][j+a[i]] += dp[i][j]
    print(dp[n][s])


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    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):
        vi = A[i]
        for j in range(S+1):
            if j+vi<=S:
                dp[i+1][j+vi] += dp[i][j]
                dp[i+1][j] += 2 * dp[i][j]
            else:
                dp[i+1][j] += 2 * dp[i][j]
    print(dp[N][S])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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] = pow(2, N, MOD)

for i in range(N):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j] # case when current element is not added
        dp[i+1][j] %= MOD
        if j + A[i] <= S: # case when current element is added
            dp[i+1][j+A[i]] += dp[i][j]//2
            dp[i+1][j+A[i]] %= MOD
print(dp[N][S])

Submission status: Wrong Answer

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] = 2**N

for i in range(N):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j] # case when current element is not added
        dp[i+1][j] %= MOD
        if j + A[i] <= S: # case when current element is added
            dp[i+1][j+A[i]] += dp[i][j]//2
            dp[i+1][j+A[i]] %= MOD
print(dp[N][S])

Submission status: Wrong Answer

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

mod=998244353

N,S=nm()
A=nl()


dp=[[0]*3001  for _ in range(3001)]#i i番目 j和がj
dp[0][A[0]]=1
dp[0][0]=2
for i in range(1,N):
    for j in range(0,3001):
        if(0<=(j-A[i])):
            dp[i][j]=dp[i-1][j-A[i]]+2*dp[i-1][j]
        else:
            dp[i][j]=2*dp[i-1][j]

ans=dp[N-1][S]
print(ans)

Submission status: Wrong Answer

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

def resolve():
    ward = 96
    n, s = map(int, input().split())
    mask = int(('1' * 32 + '0' * 64) * (s + 1) , 2)
    Mask = (1 << (s + 1) * ward) - 1
    dp = 1
    for a in map(int, input().split()):
        dp = (dp * 2) + (dp << ward * a)
        dp &= Mask
        dp = (dp & (~mask)) + ((dp & mask) >> 64) * ((1 << 64) % MOD)

    print(((dp >> s * ward) & ((1 << ward) - 1)))
resolve()

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#F
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
print(dp)
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: Wrong Answer

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%mod
    if j-a[i]>=0:
      dp[i+1][j]+=dp[i][j-a[i]]
    dp[i+1][j]%mod
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
def sub_group(A):
    ret = []
    for i in range(1 << len(A)):
        output = []
        for j in range(len(A)):
            if ((i >> j) & 1) == 1:
                output.append(A[j])
        if output != []:
            ret.append(output)
    return ret

def f(X, validGroup):
    ret = 0
    for candidate in validGroup:
        if candidate <=  X:
            ret += 1
    return ret

def main():
    MOD = 998244353
    n, s = map(int, input().split())
    a = [i for i in map(int, input().split())]
    
    validGroup = []
    sub_g = sub_group(a)
    for g in sub_g:
        if sum(g) == s:
            validGroup.append(g)

    ans = 0
    for g in sub_g:
        ans += f(g, validGroup)
    
    print(ans % MOD)


main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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