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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    # 和がSとなるように選択する
    # DP[i][wa] ... i文字目まで見て和がwaとなる個数
    DP = [[0]*(S+1) for i in range(N+1)]
    DP[0][0] = 1
    for i in range(1, N+1):
        DP[i][0] = 1
        for wa in range(S+1):
            DP[i][wa] = DP[i-1][wa]
            if 0 <= wa-A[i-1] <= S:
                DP[i][wa] += DP[i-1][wa-A[i-1]]
                DP[i][wa] %= MOD
    # print(*DP, sep="\n")

    # 組み合わせはDP[N][S]個存在する。
    # DPを逆に辿って集合を得る
    # 集合を含むような部分集合を数えあげる

    @lru_cache(maxsize=None)
    def reconstruct(n, wa):
        # nまで見て、和がwaとなるような集合のリストを返す
        # print("(n, wa)", n, wa)
        ans = []
        if wa < 0 or n < 0 or DP[n][wa] == 0:
            # print("?")
            return ans
        if n-1 >= 0 and DP[n-1][wa] != 0:
            ans.extend(reconstruct(n-1, wa))
        if DP[n][wa] != DP[n-1][wa]:
            # 文字の追加がある
            if wa-A[n-1] == 0:
                # print("only")
                ans.append({n-1})
            else:
                # print("add")
                if n-1 >= 0 and DP[n-1][wa-A[n-1]] != 0:
                    b = reconstruct(n-1, wa-A[n-1])
                    ans.extend([bb | {n-1} for bb in b])
        # print("ret, ", ans)
        return ans

    ans = 0
    for s in reconstruct(N, S):
        ans += pow(2, N - len(s), MOD)
        ans %= MOD
    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 998244353                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())

    # def my_update(counter):
    #     new_d = dict()
    #     for k, v in counter.items():
    #         new_d[k+1] = v
    #     return Counter(new_d)

    def my_update(seq, L):
        n = len(seq)
        for i in range(n-1):
            seq[i+1] += L[i]

    
    n, s = mi()
    L = lmi()
    dp = [[0] * (n + 1) for j in range(s + 1)]    # chain の長さ、場合のかず
    # print(dp)
    for i in range(n):
        for j in range(s, -1, -1):
            if j == 0 and L[i] <= s:
                dp[L[i]][1] += 1
            elif j + L[i] <= s and dp[j]:
                my_update(dp[j + L[i]], dp[j])    # counter
        # print(dp)
    
    ans = 0
    for chain_len, num in enumerate(dp[s]):
        ans = (ans + pow(2, n - chain_len, mod) * num) % mod
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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) for _ in range(n+1)] for _ in range(n+1)]
  dp[0][0][0]=1
  for i in range(1,n+1):
    val=arr[i-1]
    for j in range(i,-1,-1):
      for k in range(s,-1,-1):
        dp[i][j][k]=dp[i-1][j][k]
        if k-val>=0 and dp[i-1][j-1][k-val]!=0:
          dp[i][j][k]+=dp[i-1][j-1][k-val]
  ans=0
  for i in range(1,n+1):
    ans+=dp[n][i][s]*pow(2,n-i,mod)
    ans%=mod
  print(ans)
calc()

Submission status: Time Limit Exceeded

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]"):
    d = s(A, S, N)
    ans = 0
    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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 998244353
 
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, S = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    dp=[dict() for _ in range(S+1)]
    dp[0][0]=1
    for i,a in enumerate(A):
        for s in range(S,a-1,-1):
                for ls,val in dp[s-a].items():
                    dp[s][ls+1]=(dp[s].get(ls+1,0)+val)%mod
    ans=0
    t2=[1]
    cur=1
    for i in range(1,N+1):
        cur=2*cur%mod
        t2.append(cur)
    for l,val in dp[S].items():
        ans+=(val*t2[N-l])%mod
        ans%=mod
    #print(dp[S])
    print(ans)






if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,s=map(int,input().split())
N=[i+1 for i in range(n)]
list1=[]
pattern=[]
A=list(map(int,input().split()))

ft=0  
for i in range(1,2**n):
    list2=[]
    for j in range(n):
        if (i >> j) &1 == 1:
            list2.append(N[j])
    pattern=[]
    for x in range(1,2**len(list2)):
        pt=[]
        for y in range(len(list2)):
            if (x>>y)&1==1:
                pt.append(list2[y])
        pattern.append(pt)
   # print(pattern)

    for p in pattern:
        sum=0
        for x in p:
            sum+=A[x-1]
        if sum==s:
            ft+=1
            ft=ft%998244353
print(ft%998244353)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
from collections import defaultdict

setrecursionlimit(200000)

mod = 998244353

dub = [2]*30
for i in range(1,30):
    dub[i] = (dub[i-1]*dub[i-1])%mod

def modpow(n):
    b = 1
    for k,v in enumerate(format(n,'b')[::-1]):
        if v == '1':
            b *= dub[k]
            b %= mod
    return b

# ナップサックDPで経路復元ができたとして
# 経路長がkである経路2^(N-k)の総和を求める

N,S = map(int,input().split())
A = list(sorted(map(int,input().split()),reverse=True))
DP = [[0]*(S+1) for x in range(N+1)]

DP[0][0] = 1
su = 0
for i in range(1,N+1):
    su += A[i-1]
    for j in range(0,min(su+1,S+1)):
        if j + A[i-1] < S+1:
            DP[i][j+A[i-1]] += DP[i-1][j]
        DP[i][j] += DP[i-1][j]

D = defaultdict(int)

keiro = 0
def rec(i,j):
    global keiro,DP,ans,D
    if DP[i][j] == 0:
        return
    if i == 0:
        #print(keiro)
        D[N-keiro] += 1
        return
    if j - A[i-1] >= 0:
        #keiro.append((A[i-1],i-1))
        keiro += 1
        rec(i-1,j-A[i-1])
        #keiro.pop()
        keiro -= 1
    rec(i-1,j)

rec(N,S)

#print(*DP)

ans = 0
for k,v in D.items():
    ans += v * modpow(k)
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,S = map(int,input().split( ))
A = list(map(int,input().split( )))
a = [i for i in range(N)]
C = []
for i in range(1,N+1):
    C += list(itertools.combinations(a,i))
ans = []
for c in C:
    wa = 0
    for i in c:
        wa += A[i]
    if wa == S:
        ans.append(set(c))

count = 0
for c in C:
    for i in ans:
        if i <= set(c):
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    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:
            cc = N-i-1
            tmp = 1
            for j in range (cc):
                tmp = tmp * 2 % 998244353
            tmp *= d[i]
            ans = (ans + tmp) % 998244353
    
    print(int(ans))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,s,*a=map(int,open(0).read().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]%m)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 998244353
def main():
    n,s = map(int,input().split())
    a = list(map(int, input().split()))
    dp = [[[] for _ in range(s+1)] for _ in range(n+1)]
    dp[0][0].append([-1])
    ans = 0
    for i in range(n):
        for j in range(s,-1,-1):
            if j-a[i] < 0:
                continue
            if dp[i][j-a[i]] == []:
                continue
            for k in range(len(dp[i][j-a[i]])):
                x = copy.deepcopy(dp[i][j-a[i]][k])
                x.append(i)
                dp[i+1][j].append(x)
            if j == s and len(dp[i+1][j]):
                for e in dp[i+1][j]:
                    LEN = len(e)
                    LEN -= 1
                    ans += pow(2,n-LEN,mod)
                    ans %= mod
        for j in range(s-1,-1,-1):
            for k in range(len(dp[i][j])):
                dp[i+1][j].append(dp[i][j][k])
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,s=map(int,input().split())
a=list(map(int,input().split()))
b=list()
for i in range(n):
    b.append(0)
now=0
weight=0
ans=0
while True:
    if now>=n:
        if not 1 in b:
            break
        else:
            idx="".join(map(str,b)).rfind("1")
            b[idx]=0
            now=idx+1
            weight-=a[idx]
            continue
    if weight+a[now]<s:
        b[now]=1
        weight+=a[now]
        now+=1
        continue
    elif weight+a[now]==s:
        x=n-sum(b)-1
        y=1
        for i in range(x):
            y*=2
            y=y%998244353
        ans+=y
        now+=1
    else:
        now+=1
        
print(ans%998244353)

Submission status: Time Limit Exceeded

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:
        cc = N-i-1
        tmp = 1
        for j in range (cc):
            tmp = tmp * 2 % 998244353
        tmp *= d[i]
        ans = (ans + tmp) % 998244353

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def main():
    n,s=map(int,input().split())
    MOD=998244353
    import numpy as np
    A=list(map(int,input().split()))
    dp=[np.array([0]*(n+1)) for _ in range(s)]
    dp=[np.array([1]+[0]*n)]+dp 
    for i in range(n):
        u=A[i]
        for j in range(s,-1,-1):
            if j+u<=s:
                dp[j+u][1:]+=dp[j][:-1]
                dp[j+u]%=MOD
    #print(dp)

    w=dp[s]
    q=[2**(n-i) for i in range(n+1)]
    ans=w*q%MOD
    print(ans.sum()%MOD)
#print(w)

main()

Submission status: Time Limit Exceeded

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()))
    # 何個使って和がSになったか
    dp = [[0] * (S + 1) for _ in range(N + 1)]

    dp[0][0] = 1
    for i in range(N):
        for j in range(S + 1 - A[i])[::-1]:
            for k in range(i, -1, -1):
                # # 使わない
                # dp[i][j] += dp[i][j]
                # dp[i][j] %= MOD

                # 使う
                dp[k + 1][j + A[i]] += dp[k][j]
                dp[k + 1][j + A[i]] %= MOD

    ans = 0
    for i in range(1, N + 1):
        num = modpow(2, N - i, MOD)
        ans += dp[i][-1] * num
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 998244353
 
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, S = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    dp=[dict() for _ in range(S+1)]
    dp[0][0]=1
    for i,a in enumerate(A):
        for s in range(S,a-1,-1):
                for ls,val in dp[s-a].items():
                    dp[s][ls+1]=(dp[s].get(ls+1,0)+val)
    ans=0
    t2=[1]
    for i in range(1,N+1):
        t2.append(2*t2[-1]%mod)
    for l,val in dp[S].items():
        ans+=(val*t2[N-l])%mod
        ans%=mod
    #print(dp[S])
    print(ans)






if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(self.power_func(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(self.power_func(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __row__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

    def power_func(self,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

    def combination(self,n,r=-1):
        if r==-1:
            r = n
        #nCrの一覧を返す。rの上限も
        if (r<0) or (n<r):
            return 0
        cur = ModInt(1)
        res = []
        res.append(cur)
        for i in range(1,r+1):
            cur *= n + 1 -i
            cur /= i
            res.append(cur)
        return res

MOD = 998244353
#グローバル変数MODを決めてあげてください
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

N,S = [int(hoge) for hoge in input().split()]
A = [int(hoge) for hoge in input().split()]

DP = [[0]*(S+1) for i in range(N+1)]#DP[k][x] = i個みて和がx 
DP[0][0] = 1
Modi2 = mod_inv(2,MOD)
for i in range(N):
    a = A[i]
    #くばるDP
    for s,d in enumerate(DP[i]):
        DP[i+1][s] += DP[i][s]
        Diff = d*Modi2
        Diff %= MOD
        if s + a  <= S:
            DP[i+1][s+a] += Diff
            DP[i+1][s+a] %= MOD

two = ModInt(2)
twotwo = two ** N
print(DP[N][S] * twotwo)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
from collections import Counter

setrecursionlimit(10 ** 8)

MOD = 998244353

n, s = map(int, input().split())
la = [int(i) for i in input().split()]

dks = [[None for s_ in range(s + 1)] for i in range(n)]


def getks(i=0, s=s):
    # la[i:]
    if s < 0:
        return Counter({})
    elif i == n:
        if s == 0:
            return Counter({0: 1})
        else:
            return Counter({})
    elif dks[i][s] is not None:
        return dks[i][s]
    else:
        ks0 = getks(i + 1, s)
        ks1 = Counter({
            k + 1: v for k, v in
            getks(i + 1, s - la[i]).items()
        })
        ks = ks0 + ks1

        dks[i][s] = ks
        return ks


ks = getks()

answer = 0
for k, v in ks.items():
    answer += pow(2, n - k, MOD) * v
    answer %= MOD

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from __future__ import division, print_function

''' Hey stalker :) '''
INF = 10 ** 10
TEST_CASES = False
from _collections import defaultdict

def main():
    n, s = get_list()
    li = get_list()
    sets = defaultdict(int)
    li.sort()
    for i in li:
        new = []
        for sm, cnt in sets:
            #print(sm, cnt, sets)
            if sm+i<=s:
                new.append([(sm+i, cnt+1, ), sets[(sm, cnt, )]])
        #print(i, new)
        sets[(i, 1,)] += 1
        for i, cn in new:
            sets[i]+=cn
    res = 0
    P = 998244353
    for sm, cnt in sorted(sets):
        #print(sm, cnt, sets[(sm, cnt, )])
        if sm==s:
            res = (res+(sets[(sm, cnt, )]*pow(2, n-cnt, P)))%P
    print(res)



''' FastIO Footer: PyRival Library, Thanks @c1729 and contributors '''
import os
import sys
from bisect import bisect_left, bisect_right
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
# else:
#     sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")
get_int = lambda: int(input())
get_list = lambda: list(map(int, input().split()))

if __name__ == "__main__":
    if TEST_CASES:
        [main() for _ in range(int(input()))]
    else:
        main()

Submission status: Time Limit Exceeded

Solution code:
import copy

mod = 998244353

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

dp = [{} for i in range(s+1)]
dp[0][0] = 1

for ai in a:
    nex = []
    for i in range(s+1):
        nex.append(copy.copy(dp[i]))
    for i in range(s-ai+1):
        for k in dp[i]:
            cnt = dp[i][k]
            if k+1 in nex[i+ai]:
                nex[i+ai][k+1] += cnt
            else:
                nex[i+ai][k+1] = cnt
    dp = nex

rui = [1]

for i in range(n):
    tmp = rui[-1]
    tmp *= 2
    tmp %= mod
    rui.append(tmp)

ans = 0

for k in dp[s]:
    cnt = dp[s][k]
    ans += cnt * rui[n-k]
    ans %= mod

print(ans)