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:
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N, S = geta(int)
    A = list(geta(int))
    A.sort()
    mod = 998244353

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

    _t = pow(2, N, mod)
    for n in range(N + 1):
        dp[n][0] = _t

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

            dp[i][j] %= mod

    print(dp[N][S])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def calc():
  mod=998244353
  n,s=map(int,input().split())
  arr=list(map(int,input().split()))
  dp=[0]*(s+1)
  dp[0]=1
  ans=0
  for i in range(1,n+1):
    val=arr[i-1]
    for k in range(s,-1,-1):
      dp[k]*=2
      if k>=val and dp[k-val]!=0:
        dp[k]+=dp[k-val]
  print(dp[s])
calc()

Submission status: Wrong Answer

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+1)] #dp[i][j] = i番目まで見て重さjのものを取る方法
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

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

print(dp[N][S])            

# print(dp)

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

        dp[i][j] += dp[i-1][j]*2

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 _ in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
    dp[i][0] = dp[i-1][0]*2

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]]

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

Submission status: Wrong Answer

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

if __name__=="__main__":
    main()

Submission status: Wrong Answer

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

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
def main():
    n,s=map(int,input().split())
    A=list(map(int,input().split()))
    dp=np.array([0 for i in range(s+1)])
    dp[0]=1
    for ai in A:
        tmp=dp[:-ai].copy()
        #print(tmp)
        dp*=2
        dp[ai:]+=tmp
    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 = [[{} for i in range(S+1) ] for j in range(N+1)]
dp[0][0][0]=1
#print(dp)
for i in range(1,N+1):
  #print(i)
  a = A[i-1]
  if i==0:
    if a <= S:
      dp[i][a][1] = 1  
    continue
  for j in range(S+1):
    if len(dp[i-1][j])>0:
      for key, value in dp[i-1][j].items():
        dp[i][j][key] = value
    if j>=a:
      if len(dp[i-1][j-a]) > 0:
        for key, value in dp[i-1][j-a].items():
          if (key+1) in dp[i][j]:
            dp[i][j][key+1] += value
          else:
            dp[i][j][key+1] = value
last = dp[-1][-1]
ans = 0
for key, value in last.items():
  ans += 2**(N-key) * value
#print(last)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, s = map(int, readline().split())
a = list(map(int, readline().split()))
dp = [0] * (s + 1)
dp[0] = 1
mod = 998244353
for aa in a:
    for j in range(s, -1, -1):
        ss = j + aa
        if dp[j] != 0 and ss <= s:
            dp[ss] += dp[j]
        dp[j] *= 2 % mod
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    A, B = readline().split()
    A = int(A)
    B = int(B.replace('.', ''))
    print(A * B // 100)

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

print(dp[n][s])

Submission status: Wrong Answer

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

dp = [[0]*(3001) 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]]

print(dp[n][s])

Submission status: Wrong Answer

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

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

#H[x][y]:1,...xに制限したときに,和がyになるのは何個?
M=998244353

for x in range(N+1):
    H[x][0]=1

for x in range(1,N+1):
    for s in range(S+1):
        if s>=A[x]:
            H[x][s]=2*H[x-1][s]+H[x-1][s-A[x]]
        else:
            H[x][s]=2*H[x-1][s]

print(H[-1][-1])

Submission status: Wrong Answer

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

temp = [1] + [0] * s
for i in range(n):
    temp2 = [2] + [0] * (a[i] - 1) + [1]
    temp3 = [0] * (s + 1)
    for j in range(s + 1):
        for k in range(j + 1):
            if k < len(temp2):
                temp3[j] += temp2[k] * temp[j - k]
    temp = temp3
print(temp[s])

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    mod = 998244353
    def input(): return sys.stdin.readline().rstrip()
    n,s = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [0]*(s+1)
    dp[0] = 1
    import numpy as np
    dp = np.array(dp)
    for i in range(n):
        dp[a[i]:] = (2*dp[a[i]:]%mod + dp[:-a[i]])%mod
        dp[0] *=2
    print(dp[-1])


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

num = dp[-1][-1]
ans = 0
c = 0
while num:
    a = num % 3001
    ans += a*pow(2, N-c, MOD); ans %= MOD
    c += 1
    num //= 3001

print(ans)

Submission status: Wrong Answer

Solution code:
class Inv:
  def __init__(s, mod):
    s.MOD = mod
  def modpow(s, a, n):
    res = 1
    while n > 0:
      if n & 1:
        res = res * a % s.MOD
      a = a * a % s.MOD
      n >>= 1
    return res
  def invx(s, a):
    return s.modpow(a, s.MOD - 2)
  def invpowL(s, a, n): # a^-x (0 <= x <= n)リスト
    ia = s.invx(a)
    L = [1] * (n + 1)
    for i in range(1, n + 1):
      L[i] = L[i - 1] * ia % s.MOD
    return L
  def invL(s, n): # 0 <= x <= n 逆元リスト
    I = [0, 1]
    for i in range(2, n + 1):
      I.append(s.MOD - I[s.MOD % i] * (s.MOD // i) % s.MOD)
    return I


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

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

inv = Inv(MOD)
v = inv.invx(2)

p = inv.modpow(2, N - 1)
for i in range(1, N + 1):
  a = A[i - 1]
  if a > S: continue
  for j in range(a):
    DP[i][j] = DP[i - 1][j]
  DP[i][a] = (DP[i - 1][a] + p) % MOD
  for j in range(a + 1, S + 1):
    DP[i][j] = (DP[i - 1][j] + DP[i - 1][j - a] * v) % MOD

print(DP[-1][S])

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    mod = 998244353
    def input(): return sys.stdin.readline().rstrip()
    n,s = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [0]*(s+1)
    dp[0] = 1
    import numpy as np
    dp = np.array(dp)
    for i in range(n):
        dp[a[i]:] = (2*dp[a[i]:]%mod + dp[:-a[i]])%mod
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

MOD = 998244353
class mint:
    def __init__(self, x):
        if isinstance(x, int):
            self.x = x % MOD 
        elif isinstance(x, mint):
            self.x = x.x
        else:
            self.x = int(x) % MOD 
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __floordiv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rfloordiv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )


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

Submission status: Wrong Answer

Solution code:

MOD = 998244353
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __floordiv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rfloordiv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )


n,s = map(int, input().split())
a = list(map(int, input().split()))
import copy
dp = [[mint(0)for _ in range(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]=copy.copy(dp[i][j])
        if j-a[i]>=0:
            dp[i+1][j]+=dp[i][j-a[i]]//2
print(dp[n][s])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,s = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
for i in range(n-1, -1, -1):
    if a[i] > s:
        a.pop()
n = len(a)
if n == 0:
    print(0)
    exit()
mod = 998244353
ans = 0
dp = [[defaultdict(int) for __ in range(s+1)] for _ in range(n)]
dp[0][a[0]][1] = 1
for i in range(1, n):
    dp[i][a[i]][1] = 1
    for j in range(1, s+1):
        for k,v in dp[i-1][j].items():
            dp[i][j][k] += v
        if j >= a[i]:
            for k,v in dp[i-1][j-a[i]].items():
                dp[i][j][k+1] += v

for k,v in dp[n-1][s].items():
    ans += (pow(2, n-k, mod) * v) % mod
    ans %= mod
print(ans)

Submission status: Wrong Answer

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


print(dp[N][S])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import numpy as np

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

answer = np.zeros(S+1).astype(np.int64) # [0 for _ in range(S+1)]
power2 = 1

total = 0
for a in A:
  if a>S:
    break
  total = min(S,a+total)
  answer[a+1:total+1] = (2*answer[a+1:total+1]+answer[1:total-a+1])%mod
  answer[a] = (2*answer[a]+power2)%mod
  answer[1:a] = (2*answer[1:a])%mod
  power2 = (2*power2)%mod

print(answer[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=list(pin())

    #print(A)

    #dp[i]"s""n" i番めまで見る。n個使った。和がsになった2重の辞書…
    dp=[dict()for i  in range(N+1)]
    #sを辞書として管理するとうまく配るDPが実装できるよね
    dp[0].setdefault(0,dict())
    dp[0][0].setdefault(0,1)
    dp[-1].setdefault(S,dict())
    

    for i in range(N):#
        kouho=A[i]
        for s in dp[i]:
            ref=dp[i][s]
            for k,v in ref.items():
                ##print(k,v)
                #saiyousinai
                dp[i+1].setdefault(s,dict())
                dp[i+1][s].setdefault(k,0)
                dp[i+1][s][k]+=v
                #saiyou        
                x=s+kouho
                ##print(x)
                if x<=S:
                    dp[i+1].setdefault(x,dict())
                    dp[i+1][x].setdefault(k+1,0)
                    dp[i+1][x][k+1]+=v
                
    temp=(dp[-1][S])
    ans=0
    for p,q in temp.items():
        if N-p>=0:
            ans+=q*(2**(N-p))
    print(ans)
#%%submit!
resolve()

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
fac=[1,1]
for i in range(2,3010):
    fac.append(fac[-1]*i%mod)
ifac=[pow(i,mod-2,mod) for i in fac]

def comb(a,b):
    return(fac[a]*ifac[a-b]*ifac[b]%mod)


dp=[defaultdict(int) for n in range(3001)]
for n in range(N):
    a=A[n]
    for s in range(0,3000)[::-1]:
        if s+a<=3000:
            for h in dp[s]:
                dp[s+a][h+1]+=dp[s][h]
    dp[a][1]+=1
c=0
for a in dp[S]:
    c+=comb(N,a)*dp[S][a]
    c%=mod
print(c)

Submission status: Wrong Answer

Solution code:
PRIME = 998244353

n, s = map(int, input().split())
a = list(map(int, input().split()))
l = [[0 for i in range(n + 1)] for j in range(s + 1)]
l[0][0] = 1

for i in range(n):
  for j in range(s, -1, -1):
    if j + a[i] <= s:
      for k in range(i + 1):
        l[j + a[i]][k + 1] += l[j][k]

ans = 0
for j in range(n):
  if l[s][j] != 0:
    ans += l[s][j] * pow(2, n - j, PRIME)
    ans %= PRIME
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N, S = geta(int)
    A = list(geta(int))
    A.sort()
    mod = 998244353

    memo = dict()

    def dfs(n, s):
        if (n, s) not in memo:
            if s == 0:
                ret = pow(2, N, mod)
            elif n == 0 or s < 0:
                ret = 0
            else:
                ret = dfs(n - 1, s - A[n - 1]) // 2 + dfs(n - 1, s)
                ret %= mod

            memo[(n, s)] = ret

        return memo[(n, s)]

    print(dfs(N, S))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N, S = geta(int)
    A = list(geta(int))
    A.sort()
    mod = 998244353

    memo = dict()

    def dfs(n, s):
        if (n, s) not in memo:
            if s == 0:
                ret = pow(2, N)
            elif n == 0 or s < 0:
                ret = 0
            else:
                ret = dfs(n - 1, s - A[n - 1]) // 2 + dfs(n - 1, s)

            memo[(n, s)] = ret

        return memo[(n, s)]

    print(dfs(N, S))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 998244353

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

a.sort()

while a[-1] > s:
    a.pop(-1)
    if a == []:
        print(0)
        exit()

su = sum(a)
if su < s:
    print(0)
    exit()
if su == s:
    print(1)
    exit()

mark = [[] for _ in range(s+1)]
dp = [[0] * (len(a)+1) for _ in range(s+1)]
for i in a:
    for k in range(s-i, 0, -1):
        for l in mark[k]:
            if dp[k+i][l+1] == 0:
                mark[k+i].append(l+1)
            dp[k+i][l+1] += dp[k][l]
    if dp[i][1] == 0:
        mark[i].append(1)
    dp[i][1] += 1

ans = 0
for i in mark[s]:
    ans += pow(2, n - i, mod) * dp[s][i]
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
n,s = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
flag = True
ans = 0
while flag:
    check = 0
    num = 0
    c = True
    for i in a:
        check += i
        num += 1
        if check > s:
            a.pop(0)
            c = False
            if num == 1:
                flag = False
            break
        elif check == s:
            a.pop(0)
            if num == 1:
                flag = False
            break
    if c:
        ans+=2**(n-num)
print(ans)

Submission status: Wrong Answer

Solution code:
class Combination:
    def __init__(self, n, mod):
        self.mod = mod

        # self.fac[i] ≡ i! (factorial:階乗)
        l = [1]
        num = 1
        for i in range(1, n+1):
            num *= i
            num %= mod
            l.append(num)
        self.fac = l.copy()

        # self.rec[i] ≡ 1 / i! (reciprocal:逆数)
        num = pow(num, mod-2, mod)
        l = [1 for i in range(n+1)]
        l[n] = num
        for i in range(n-1, 0, -1):
            num *= i + 1
            num %= mod
            l[i] = num
        self.rec = l.copy()

    # comb(n, r) ≡ nCr
    def comb(self, n, r):
        return self.fac[n] * self.rec[r] * self.rec[n - r] % self.mod

mod = 998244353

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

#c = Combination(n, mod)

a.sort()

while a[-1] > s:
    a.pop(-1)
    if a == []:
        print(0)
        exit()

su = sum(a)
if su < s:
    print(0)
    exit()
if su == s:
    print(1)
    exit()

mark = [[] for _ in range(s+1)]
dp = [[0] * (len(a)+1) for _ in range(s+1)]
for i in a:
    for k in range(s-i, 0, -1):
        for l in mark[k]:
            if dp[k+i][l+1] == 0:
                mark[k+i].append(l+1)
            dp[k+i][l+1] += dp[k][l]
    if dp[i][1] == 0:
        mark[i].append(1)
    dp[i][1] += 1

print(a)
print(dp)

ans = 0
for i in mark[s]:
    ans += pow(2, n - i, mod) * dp[s][i]
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
PRIME = 998244353

n, s = map(int, input().split())
a = list(map(int, input().split()))
l = [[] for j in range(s + 1)]
l[0] = [0]

for i in range(n):
  for j in range(s, -1, -1):
    if j + a[i] <= s:
      for _l in l[j]:
        l[j + a[i]].append(_l + 1)

ans = 0
for i in l[s]:
  ans += pow(2, n - i, PRIME)
print(ans)

Submission status: Wrong Answer

Solution code:
n, s = map(int, input().split())
a = list(map(int, input().split()))
l = [[] for j in range(s + 1)]
l[0] = [0]

for i in range(n):
  for j in range(s, -1, -1):
    if j + a[i] <= s:
      for _l in l[j]:
        l[j + a[i]].append(_l + 1)

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

Submission status: Wrong Answer

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

c = {}
for i in range(2**n-1):
    f = 0
    count = 0
    for j in range(n):
        if (i >> j) & 1:
            f += a[j]
            count +=1
    if f == s:
        if count in c:
            c[count] += 1
        else:
            c[count] = 1

ans = 0
for i in c:
    k = 2**(n-i)
    ans += k*c[i]

ans = ans % 998244353
print(ans)

Submission status: Wrong Answer

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

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

dp[0][0][0] = 1
for i in range(N):
  ai = A[i]
  for j in range(S-ai+1):
    for k in range(i+1):
      dp[i+1][k+1][j+ai] += dp[i][k][j]
  for j in range(S+1):
    for k in range(i+1):
      dp[i+1][k][j] += dp[i][k][j]

ans = 0
for i in range(1, N+1):
  ans += dp[N][i][S]*pow(2,(N-i),998244353)
  
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

subsets=[]
ans = 0
for i in range(min(s,len(items) + 1)):
    for c in combinations(items, i):
        if sum(c) == s:
            ans += 2**(n-len(c))
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys
from typing import Tuple, Dict

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62

MOD = 998244353  # type: int


# if sys.argv[-1] == 'ONLINE_JUDGE':
#     from numba.pycc import CC
#
#     cc = CC('my_module')
#
#
#     @cc.export('s', '(i8[:],i8[:],i8)')

def s(A, S: int, N: int):
    d = collections.defaultdict(dict)
    d[0][0] = 1  # left:vale right:count
    for i, a in enumerate(A):
        for left in sorted(d.keys(), reverse=True):
            if left + a > S:
                continue
            for right in d[left]:
                if right + 1 in d[left + a]:
                    d[left + a][right + 1] += d[left][right]
                else:
                    d[left + a][right + 1] = d[left][right]
    return d


def solve(N: int, S: int, A: "List[int]"):
    d1 = s(A[:N // 2], S, N)
    d2 = s(A[N // 2:], S, N)

    ans = 0
    for s1 in d1:
        s2 = S - s1
        for k1, v1 in d1[s1].items():
            for k2, v2 in d2[s2].items():
                pat = v1 + v2 -1 
                ans += pat * 2 ** (N - k1 - k2)
                ans %= 998244353

    # for count in d[S]:
    #     ans += d[S][count] * 2 ** (N - count)
    #     ans %= 998244353
    print(ans)


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

Solution code:
import math
def combinations_count(n, r):
    if n-r<0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
mod=998244353
n,s=map(int,input().split())
a=list(map(int,input().split()))
dp=[dict() for i in range(s+1)]
for i in range(n):
    if a[i]<=s:
        if 1 in dp[a[i]]:
            dp[a[i]][1]+=1
        else:
            dp[a[i]][1]=1
for i in range(1,s+1):
    for k in range(i,s+1):
        if k+i<=s:
            if k!=i:
                for j in dp[i]:
                    if j+1 in dp[k+i]:
                        dp[k+i][j+1]+=dp[i][j]
                        dp[k+i][j+1]%=mod
                    else:
                        dp[k+i][j+1]=dp[i][j]
                        dp[k+i][j+1]%=mod
            else:
                for j in dp[i]:
                    if j==1:
                        if j+1 in dp[k+i]:
                            dp[k+i][j+1]+=combinations_count(dp[i][j],2)
                            dp[k+i][j+1]%=mod
                        else:
                            dp[k+i][j+1]=combinations_count(dp[i][j],2)
                            dp[k+i][j+1]%=mod
                    else:
                        if j+1 in dp[k+i]:
                            dp[k+i][j+1]+=dp[i][j]
                            dp[k+i][j+1]%=mod
                        else:
                            dp[k+i][j+1]=dp[i][j]
                            dp[k+i][j+1]%=mod

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 998244353


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


def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


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

    def func():
        # now, cnt, sum
        q = deque([(0, 0, 0)])

        ans = 0
        while q:
            n, c, s = q.pop()

            if s > S:
                continue

            if n >= N:
                continue

            if s == S:
                ans += modpow(2, N - c, MOD)
                ans %= MOD
                continue

            # 使わない
            q.append((n + 1, c, s))

            # 使う
            q.append((n + 1, c + 1, s + A[n]))

        return ans

    ans = func()

    print(ans)


if __name__ == "__main__":
    main()