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 Counter

def main():
    input = sys.stdin.readline
    n, s = map(int, input().split())
    counter = Counter([int(x) for x in input().split()])
    mod = 998244353
    
    dp = [dict() for _ in range(s+1)]
    
    judge = dict()
    for key, value in counter.items():
        for j in range(s-1, -1, -1):
            if dp[j] != judge and key+j <= s:
                index = 1
                mono = 1
                mono2 = key
                mono3 = 1
                while key*index+j <= s and index <= value:
                    mono *= (mono2*pow(mono3, mod-2, mod))%mod
                    mono %= mod
                    mono2 -= 1
                    mono3 += 1
                    for k, v in dp[j].items():
                        if k+1 in dp[key*index+j]:
                            dp[key*index+j][k+1] = (v*mono%mod+dp[key*index+j][k+1])%mod
                        else:
                            dp[key*index+j][k+1] = v%mod
                    index += 1
            if j == 0 and key <= s:
                index = 1
                mono = 1
                mono2 = key
                mono3 = 1
                while key*index <= s and index <= value:
                    mono *= (mono2*pow(mono3, mod-2, mod))%mod
                    mono %= mod
                    mono2 -= 1
                    mono3 += 1
                    if 1 in dp[key]:
                        dp[key][1] = (dp[key][1]+1)%mod
                    else:
                        dp[key][1] = 1
                    index += 1
    ans = 0
    count = 1
    for k in range(n, 0, -1):
        if k in dp[s]:
            ans += (count*dp[s][k])%mod
            ans %= mod
        count *= 2
        count %= mod
    
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N,S = map(int,S().split())
A = [0] + LI()
mod = 998244353

from collections import defaultdict

dp = defaultdict(int)


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

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

dp[0][0] = 1

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

        dp[i+1][j] += dp[i][j]

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

print(ans)

Submission status: Wrong Answer

Solution code:
N,S=map(int,input().split())
A=list(map(int,input().split()))
#dp[i]{:}:iまでを使って数字k個でjを作る方法
dp=[[{}]*(S+1) for _ in range(N+1)]
dp[0][0]={0:1}
for i in range(1,N+1):
  for j in range(S):
    if j+A[i-1]>S:
      break
    for k,v in dp[i-1][j].items():
      if not(k+1 in dp[i][j+A[i-1]]):
        dp[i][j+A[i-1]][k+1]=v
      else:
        dp[i][j+A[i-1]][k+1]+=v

print(dp[N][S])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)
from itertools import accumulate
from collections import defaultdict


def read():
    N, S = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, S, A


def solve(N, S, A, MOD=998244353, INF=10**9):
    A = list(sorted(A))
    B = list(accumulate(A))
    dp = [[0 for j in range(S+1)] for i in range(N+1)]
    G = [[-1 for j in range(2)] for i in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 1
    for i in range(N):
        for j in range(1, S+1):
            if j - A[i] >= 0:
                dp[i+1][j] = dp[i][j-A[i]] + dp[i][j]
                if dp[i][j-A[i]] > 0:
                    G[i+1][1] = i
                if dp[i][j] > 0:
                    G[i+1][0] = i

    pairs = []

    def dfs(i, pair):
        if i == 0:
            pairs.append(pair)
        else:
            if G[i][0] >= 0:
                dfs(i-1, pair)
            elif G[i][0] >= 0:
                dfs(i-1, [i] + pair)
        
    dfs(N, [])
    print(pairs)
    return -1



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

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    md=998244353
    n,s=MI()
    aa=LI()
    dp=[0]*(s+1)
    dp[0]=1
    inv=pow(2,md-2,md)
    for k,a in enumerate(aa):
        for i in range(s-a,-1,-1):
            dp[i+a]=(dp[i+a]+dp[i]*inv)%md
        #print(k,dp)
    ans=dp[s]*pow(2,n,md)
    print(ans)

main()

Submission status: Wrong Answer

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

mod=998244353

if a[0]>s:
    print(0)
    exit()

#i番目以下で合計がjの個数
#dp[i][j]
dp=[[0]*(s+1) for _ in range(n)]


dp[0][a[0]]=1
#print(dp)
for i in range(1,n):
    #print(">",i)
    if a[i]<=s:
        for j in range(s+1):
            #print(">>",j,a[i])
            if j<a[i]:
                dp[i][j]=max(dp[i-1][j],dp[i][j])%mod
                #print("a",dp)
            elif j==a[i]:
                dp[i][j]+=(dp[i-1][j]+1)%mod
                #print("b",dp)
            else:
                dp[i][j]+=(dp[i-1][j-a[i]])%mod
                #print("c",dp)
    else:
        for j in range(s+1):
            dp[i][j]=dp[i-1][j]


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

Submission status: Wrong Answer

Solution code:
class Factorial:
    def __init__(self, n, mod=10**9+7):
        self.fac = [0] * (n+1)
        self.ifac = [0] * (n+1)
        self.fac[0] = 1
        self.ifac[0] = 1
        self.mod = mod
        modmod = self.mod - 2
        for i in range(n):
            self.fac[i+1] = self.fac[i] * (i+1) % self.mod
            self.ifac[i+1] = self.ifac[i] * pow(i+1, modmod, self.mod) % self.mod

    def comb(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        tmp =  self.ifac[n-r] * self.ifac[r] % self.mod
        return tmp * self.fac[n] % self.mod

    def perm(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        return (self.fac[n] * self.ifac[n-r]) % self.mod
import math

def resolve():
    n, s = map(int, input().split())
    mod = 998244353
    dp = [0 for i in range(s + 1)]
    aa = [i for i in map(int, input().split())]
    bb = [i for i in aa if i <= s]
    cc = [i for i in aa if i > s]

    dp[0] = 1
    for a in bb:
        for i in range(s+1-a)[::-1]:
            if dp[i]:
                dp[i+a] = (dp[i] + dp[i+a])
    ss = sum(dp[:-1])
    print(2**n-1 - math.factorial(len(cc)) * ss)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
n,s=map(int,input().split())
l=list(map(int,input().split()))
dp=[[0]*(s+1) for i in range(n+1)]
dp[0][0]=1
mod=998244353
for i in range(n):
  for j in range(s+1):
    if j>=l[i]:
      dp[i+1][j]=(dp[i][j-l[i]]+dp[i][j])%mod
    else:
      dp[i+1][j]=dp[i][j]
ans=0
memo=2
for i in range(n):
  now=dp[-i-1][-1]-dp[-i-2][-1]
  ans=(ans+now*memo)%mod
  memo=memo*2
print(ans)

Submission status: Wrong Answer

Solution code:
print(3296)

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

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 998244353
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,S = LI()
    A = [0] + LI()
    dp = [[0] * (S+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(1,N+1):
        for j in range(1,S+1):
            if j >= A[i]:dp[i][j] = max(dp[i-1][j],dp[i-1][j-A[i]]+1)
            else: dp[i][j] = dp[i-1][j]

    ans = 0
    for i in range(1,N):
        if dp[i][-1] > 0:
            ans = (ans + pow(2,N-dp[i][-1],MOD)) % MOD
    print(ans)

if __name__ == '__main__':
    main()

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+ai]
  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 collections import Counter
N,S=list(map(int,input().split()))
A=list(map(int,input().split()))
result=[]
for i in range(2**N):
    B=[]
    for j in range(N):
        if ((i>>j)&1):
            B.append(A[j])
    result.append(B)
C=[]
for i in result:
    if sum(i)==S:
        C.append(i)
D=[]
for i in C:
    D.append(Counter(i))
ans=0
for j in D:
    for k,value in j.items():
        for i in result:
            if Counter(i)[k]>=value:
                ans+=1
print(ans)

Submission status: Wrong Answer

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

bins = [1 for _ in range(n+1)]
for i in range(1, n + 1):
    bins[i] = (2 * bins[i-1]) % MOD

dp = [defaultdict(lambda: 0) for _ in range(s+1)]
dp[0][0] = 1
for v in a:
    if v > s:
        continue
    for i in reversed(range(s-v+1)):
        for length, cnt in dp[i].items():
                dp[i+v][length+1] += cnt

ans = 0

for k, v in dp[s].items():
    ans += (bins[n] // bins[k]) * v
    ans %= MOD

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())


ans = 0
memo = {}


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

    def dfs(n, s, ret):
        if (n, s, ret) not in memo:

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

        return memo[(n, s, ret)]

    print(dfs(N, S, 0))


if __name__ == "__main__":
    main()

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:
n,s=map(int,input().split())
A=list(map(int,input().split()))
k=n
for i in range(n):
    if A[i]>s:
        k=i
        break
del A[k:n]

from itertools import combinations
sub=[]
for i in range(len(A) + 1):
    for c in combinations(A, i):
        if sum(c)==s:
            sub.append(c)

ans=0
for i in sub:
    ans+=(2**(n-len(i)))

print(ans%998244353)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,s = na()
a = na()
mod = 998244353

dp = [[] for i in range(3001)]
dp[0] = [0]

for i in a:
    if s+1-i<0: continue
    for j in range(s+1-i)[::-1]:
        for k in dp[j]:
            dp[j+i].append(k+1)

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def modpow(val, n, mod):
    ret = 1
    while n:
        if n & 1:
            ret = (ret * val) % mod
        val = (val * val) % mod
        n = n >> 1
    return ret


def part_sum(a_list, target):
    mod = 998244353
    N = len(a)
    dp = [[[0 for i in range(N+1)] for j in range(target+1)]
          for k in range(N+1)]
    # length, val, cnt
    for i in range(N+1):
        dp[i][0][0] = 1

    for i in range(N):
        for j in range(target+1):
            for k in range(1, N+1):
                val = 0
                if a_list[i] <= j:
                    val += dp[i][j-a[i]][k-1] % mod
                val += dp[i][j][k] % mod
                dp[i+1][j][k] = val
    return dp


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

mtx = part_sum(a, s)

val_mxt = mtx[-1][s]
ret = 0

for i, val in enumerate(val_mxt):
    kosu = modpow(2, (n - i), 998244353)
    ret += kosu * val

print(ret)

Submission status: Wrong Answer

Solution code:
import itertools
N,S=map(int,input().split())
A=list(map(int,input().split()))
if S>sum(A)//2:
  S=sum(A)-S
a=0
for i in range(1,S+1):
  for c in itertools.combinations(A, i):
    if sum(c) == S:
      a+=2**(N-i)
      a=a%998244353
print(a)

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

import copy

N,S = IL()
A = IL()

dic = DD(int)
dic[0] = 1

for a in A:
  koushinyotei = []
  for s,n in dic.items():
    if s+a <= S:
      koushinyotei.append((s+a,n))
    dic[s] = n*2
  #for s,n in koushinyotei:
  #  dic[s] += n
    
print(dic[S]%998244353)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(5000)
MOD=998244353
def dfs(d,tot,num):
    global A,N,S,how
    if tot==S:
        how[num]+=1
        return
    if d==N:
        return
    if tot+A[d]<=S:
        dfs(d+1,tot+A[d],num+1)
    if d==0 or (d>0 and A[d]!=A[d-1]):
        dfs(d+1,tot,num)
    else:
        nex=N
        for i in range(d,N):
            if A[i]!=A[d]:
                nex=i
                break
        dfs(nex,tot,num)
    

N,S=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
how=[0]*(N+1)
dfs(0,0,0)
cur=1
res=0
for i in range(N,0,-1):
    res=(res+(how[i]*cur))%MOD
    cur=(cur*2)%MOD
print(res)

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
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
#Σ2 ** 他の要素の数
N, S = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
ans = 0
ind = []
for i in ind:
    ans += 2 ** (N - i)
ans %= 998244353
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(5000)
MOD=998244353
def dfs(d,tot,num):
    global A,N,S,how
    if tot==S:
        how[num]+=1
        return
    if d==N:
        return
    if tot+A[d]<=S:
        dfs(d+1,tot+A[d],num+1)
    if d==0 or (d>0 and A[d]!=A[d-1]):
        dfs(d+1,tot,num)
    else:
        nex=N
        for i in range(d,N):
            if A[i]!=A[d]:
                nex=i
                break
        dfs(nex,tot,num)
    

N,S=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
how=[0]*(N+1)
dfs(0,0,0)
cur=1
res=0
for i in range(N,0,-1):
    res+=(how[i]*cur)%MOD
    cur=(cur*2)%MOD
print(res)

Submission status: Wrong Answer

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
dp = np.zeros(S+1, np.int32)
dp[0] = 1
for a in A:
    prev = dp.copy()
    dp[a:] += dp[:-a]
    dp += prev
    dp %= MOD

answer = dp[S]
print(answer%MOD)

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

import copy

N,S = IL()
A = IL()

dic = DD(int)
dic[0] = 1

for a in A:
  koushinyotei = []
  for s,n in dic.items():
    if s+a <= S:
      koushinyotei.append((s+a,n))
  for s,n in dic.items():
    dic[s] = n*2
  for s,n in koushinyotei:
    dic[s] += n
    
print(dic[S])

Submission status: Wrong Answer

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

class Facts():
    # O(max_num)
    def __init__(self, max_num=3*10**3, p=MOD):
        self.p = p
        self.max_num = max_num
        self.fact = [1] * (self.max_num + 1)
        for i in range(1, self.max_num + 1):
            self.fact[i] = self.fact[i-1] * i
            self.fact[i] %= self.p

    def comb(self, n, k):
        # nCk mod p with memo
        # O(log(p))
        if n < 0 or k < 0 or n < k:
            return 0
        if n == 0 or k == 0:
            return 1
        a = self.fact[n]
        b = self.fact[k]
        c = self.fact[n-k]
        return (a*self.power_func(b, self.p-2) *
                self.power_func(c, self.p-2)) % self.p

    def power_func(self, a, b):
        # a^b mod p
        # O(log(b))
        ans = 1
        while b > 0:
            if b & 1:
                ans = ans * a % self.p
            a = a * a % self.p
            b >>= 1
        return ans

facts = Facts()
bins = [1 for _ in range(n+1)]
for i in range(1, n + 1):
    bins[i] = (2 * bins[i-1]) % MOD

dp = [[] for _ in range(s+1)]
dp[0] = [0]
for v in a:
    if v > s:
        continue
    for i in reversed(range(s-v+1)):
        if dp[i]:
            for cnt in dp[i]:
                dp[i+v].append(cnt+1)
ans = 0
for v in dp[s]:
    ans += bins[n] // bins[v]

print(ans)

Submission status: Wrong Answer

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


def ps(a,A):
    p=998244353
    #初期化
    #N=len(a)
    dp=[[[0 for i in range(N+1)] for j in range(A+1)] for k in range(N+1)]
    #dp=[[0 for i in range(A+1)] for j in range(N+1)]
    dp[0][0][0]=1

      #DP
    for i in range(N):
        for k in range(N):
            for j in range(A+1):
                if a[i]<=j: #i+1番目の数字a[i]を足せるかも[]
                    dp[i+1][j][k+1]=dp[i][j-a[i]][k]+ dp[i][j][k+1]% p
                else: #入る可能性はない
                    dp[i+1][j][k]=dp[i][j][k]%p
    return dp[N][A][1:]


d = ps(a,A)

ans = 0
for i in range(len(d)):
    if d[i] > 0:
        tmp = ((2**N) / (2**(i+1))) * d[i]
        ans = (ans + tmp) % 998244353

print(int(ans))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(5000)
MOD=998244353
def dfs(d,tot,num):
    global A,N,S,how
    if tot==S:
        how[num]+=1
        return
    if d==N:
        return
    if tot+A[d]<=S:
        dfs(d+1,tot+A[d],num+1)
    dfs(d+1,tot,num)
        
    

N,S=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
how=[0]*(N+1)
dfs(0,0,0)
cur=1
res=0
for i in range(N,0,-1):
    res+=(how[i]*cur)%MOD
    cur=(cur*2)%MOD
print(res)

Submission status: Wrong Answer

Solution code:
def subsets(nums):
    output = []
    for i in range(1, len(nums)):
        backtrack(0, nums, i, [], output)

    return output


def backtrack(start, nums, size, curr, output):
    if len(curr) == size:
        output.append(curr[:])

    for i in range(start, len(nums)):
        curr.append(nums[i])
        backtrack(i + 1, nums, size, curr, output)
        curr.pop()


def count_subsets(num, sum):
    n = len(num)
    dp = [0 for _ in range(sum+1)]
    dp[0] = 1

    # with only one number, we can form a subset only when the required sum is equal to the number
    for s in range(1, sum+1):
        dp[s] = 1 if num[0] == s else 0

    # process all subsets for all sums
    for i in range(1, n):
        for s in range(sum, -1, -1):
            if s >= num[i]:
                dp[s] += dp[s - num[i]]

    return dp[-1]


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

result = count_subsets(sub_sets, S)

print(result % 998244353)