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:
import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,s = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    mod = 998244353
    two = [1]*(n+1)
    for i in range(n):
        two[i+1] = two[i]*2%mod
    dp = np.zeros((n+1,s+1),dtype = int)
    for i,ai in enumerate(a):
        if ai > s:
            continue
        for j in range(n):
            dp[n-j][ai:] += dp[n-j-1][:-ai]
        dp[1][ai] += 1
    ans = 0
    for i in range(n+1):
        dpi = dp[i]
        ans = (ans+(dpi[s]*two[n-i])%mod)%mod
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
mod = 998244353
input = lambda:sys.stdin.readline().strip()
n,s = map(int,input().split())
dp = [0]*(6030)
a = list(map(int,input().split()))
dp[0] = 1
for i in range(n):
    for j in range(s,-1,-1):
        dp[j+a[i]] = (dp[j+a[i]]+dp[j])%mod 
        dp[j] = (dp[j]*2)%mod 
print(dp[s])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,S = LI()
A = LI()

beki = [1]*(N+1)
for i in range(1,N+1):
    beki[i] = beki[i-1]*2
    beki[i] %= mod

inv2 = pow(2,mod-2,mod)

d = [0]*(S+1)
d[0] = beki[N]

ans = 0
for i in range(N):
    if 0 <= S-A[i] <= S:
        ans += d[S-A[i]]*inv2
        ans %= mod
    diff = [0]*(S+1)
    for k in range(S-A[i]+1):
        diff[k+A[i]] = d[k]*inv2
    for k in range(S+1):
        d[k] += diff[k]

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,S = LI()
A = LI()

beki = [1]*(N+1)
for i in range(1,N+1):
    beki[i] = beki[i-1]*2
    beki[i] %= mod

inv2 = pow(2,mod-2,mod)

d = defaultdict(int)
d[0] = beki[N]

ans = 0
for i in range(N):
    if 0 <= S-A[i] <= S:
        ans += d[S-A[i]]*inv2
        ans %= mod
    diff = defaultdict(int)
    for k in d.keys():
        if 0 < k+A[i] <= S:
            diff[k+A[i]] = d[k]*inv2
    for k in diff.keys():
        d[k] += diff[k]

print(ans)

Submission status: Time Limit Exceeded

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

dp=[0]*(S+1)
dp[0]=pow(2,N,MOD)
div=pow(2,MOD-2,MOD)

m=0
for a in A:
    m+=a
    for i in range(min(m,S),a-1,-1):
        dp[i]=(dp[i]+dp[i-a]*div)%MOD
print(dp[S])

Submission status: Time Limit Exceeded

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


dp=[defaultdict(int) for n in range(3001)]
for n in range(N):
    a=A[n]
    for s in range(0,S+1)[::-1]:
        if s+a<=S:
            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+=pow(2,N-a,mod)*dp[S][a]
    c%=mod
print(c)

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [0] * (S + 1)
dp[0] = pow(2, N, mod)
div2 = pow(2, mod - 2, mod)
m = 0
for a in A:
    m += a
    for i in reversed(range(a, min(S, m) + 1)):
        dp[i] = (dp[i] + dp[i - a] * div2) % mod

print(dp[S])

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,s = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    mod = 998244353
    two = [1]*(n+1)
    for i in range(n):
        two[i+1] = two[i]*2%mod
    dp = np.zeros((n+1,s+1),dtype = int)
    for i,ai in enumerate(a):
        if ai > s:
            continue
        dp1 = np.zeros((n+1,ai),dtype=int)
        dp2 = np.zeros((1,s+1-ai),dtype=int)
        dp3 = np.array([l[:s+1-ai] for l in dp[:-1]])
        dp4 = np.block([[dp2],[dp3]])
        dp5 = np.block([dp1,dp4])
        dp += dp5
        dp[1][ai] += 1
    ans = 0
    for i in range(n+1):
        dpi = dp[i]
        ans = (ans+(dpi[s]*two[n-i])%mod)%mod
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [0] * (S + 1)
dp[0] = pow(2, N, mod)
div2 = pow(2, mod - 2, mod)
for a in A:
    for i in reversed(range(a, S + 1)):
        dp[i] = (dp[i] + dp[i - a] * div2) % mod
print(dp[S])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N, S = map(int, input().split())
As = list(map(int, input().split()))
As.sort(reverse=True)

cts = [Counter() for _ in range(min(S, N)+1)]
cts[0][0] = 1
for a in As:
    for i in range(min(S, N)-1, -1, -1):
        ct = cts[i]
        for v, n in ct.items():
            if v+a <= S:
                cts[i+1][v+a] += n

ans = 0
MOD = 998244353
for i in range(1, min(S, N)+1):
    ct = cts[i]
    ans += ct[S] * pow(2, (N-i), MOD)
    ans %= MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

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


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+=pow(2,N-a,mod)*dp[S][a]
    c%=mod
print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N, S = map(int, input().split())
As = list(map(int, input().split()))

cts = [Counter() for _ in range(min(S, N)+1)]
cts[0][0] = 1
for a in As:
    for i in range(min(S, N)-1, -1, -1):
        ct = cts[i]
        for v, n in ct.items():
            if v+a <= S:
                cts[i+1][v+a] += n

ans = 0
MOD = 998244353
for i in range(1, min(S, N)+1):
    ct = cts[i]
    ans += ct[S] * pow(2, (N-i), MOD)
    ans %= MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

#print(N,S,nums)

count=0
for i in range(len(nums)):
  #print("#",i)
  _list = list(itertools.combinations(nums, i+1))
  #print("_list=",_list)
  
  for sub_list in _list:
    #print("T{}=",sub_list)
    _nums = list(sub_list)
    #print("_nums=",_nums)
    for l in range(len(_nums)):
      __list = list(itertools.combinations(_nums, l+1))
      for k in __list:
        if sum(k) == S:
          #print(k,":",sum(k))
          count +=1
    
print(count%998244353)

Submission status: Time Limit Exceeded

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

    ft=0  
    dict={}
    for i in range(n+1):
        dict[i]=[]
    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
            if p in dict[len(p)]:
                ft+=1
            else:
                for x in p:
                    sum+=A[x-1]
                if sum==s:
                    dict[len(p)].append(p)
                    ft+=1
                    ft=ft%998244353
    print(ft%998244353)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,s = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    mod = 998244353
    two = [1]*(n+1)
    for i in range(n):
        two[i+1] = two[i]*2%mod
    dp = np.zeros((n+1,s+1),dtype = int)
    for i,ai in enumerate(a):
        if ai > s:
            continue
        dp1 = np.zeros((n+1,ai),dtype=int)
        dp2 = np.zeros((1,s+1-ai),dtype=int)
        dp3 = np.array([l[:s+1-ai] for l in dp[:-1]])
        dp4 = np.block([[dp2],[dp3]])
        dp5 = np.block([dp1,dp4])
        dp += dp5
        dp[1][ai] += 1
    ans = 0
    for i in range(n+1):
        ans = (ans+(dp[i][s]*two[n-i])%mod)%mod
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 998244353
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    
    dp = [[0] * (S + 1) for i in range(N + 1)]
    dp[0][0] = 1
    
    for i, a in enumerate(A, start=1):
        # i - 1 番目までの数で 合計が X になる組み合わせが
        # dp[i-1][X] 個あるのであれば、
        # そのdp[i-1][X] 個 のそれぞれに対してAi を加える/加えないの
        # 2パターンが考えられるので、dp[i-1]を2倍する
        dp[i] = [2 * x for x in dp[i-1]]
        # さらに、i - 1 番目までの数で 合計が X - Ai になる組み合わせが
        # dp[i-1][X - Ai] 個ある場合、
        # i番目の数(Ai)を足すことで合計をXにできる
        for j in range(S + 1 - a):
            if dp[i-1][j] != 0:
                dp[i][j + a] += dp[i-1][j]
        
        # 大きくなりすぎないように逐次MODをとる
        for j in range(S + 1):
            dp[i][j] %= MOD

    # print(*dp, sep='\n')
    print(dp[N][S])

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  
dict={}
for i in range(n+1):
    dict[i]=[]
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
        if p in dict[len(p)]:
            ft+=1
        else:
            for x in p:
                sum+=A[x-1]
            if sum==s:
                dict[len(p)].append(p)
                ft+=1
                ft=ft%998244353
print(ft%998244353)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

X = [([0], s)]
y = defaultdict(int)
for ai in a:
    Xi = []
    for l, r in X:
        if r < ai:
            continue
        Xi.append((l, r))
        if r == ai:
            y[len(l)] += 1
            continue
        elif r - ai >= ai:
            Xi.append((l + [ai], r - ai))
    X = Xi

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,S = LI()
A = LI()

beki = [1]*(N+1)
for i in range(1,N+1):
    beki[i] = beki[i-1]*2
    beki[i] %= mod

inv2 = pow(2,mod-2,mod)

d = defaultdict(int)
d[0] = beki[N]

ans = 0
for i in range(N):
    if 0 <= S-A[i] <= S:
        ans += d[S-A[i]]*inv2
        ans %= mod
    kl = list(d.keys())
    diff = defaultdict(int)
    for k in kl:
        if 0 < k+A[i] <= S:
            diff[k+A[i]] = d[k]*inv2
    for k in diff.keys():
        d[k] += diff[k]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, copy
# import numpy as np
# import scipy
from collections import defaultdict
input = sys.stdin.readline
mod = 998244353
def main():
    n,s = map(int,input().split())
    a = list(map(int, input().split()))
    dp = [[defaultdict(int) for _ in range(s+1)] for _ in range(n+1)]
    dp1 = [[defaultdict(int) for _ in range(s+1)] for _ in range(n+1)]
    dp2 = [0 for _ in range(n+1)]
    dp2[0] = 1
    for i in range(n):
        dp2[i+1] = dp2[i]*2
        dp2[i+1] %= mod
    dp[0][0][0] = 1
    dp1[0][0][0] = 1
    ans = 0
    for i in range(n):
        for j in range(s,-1,-1):
            if j-a[i] < 0:
                continue
            if not dp1[i][j-a[i]]:
                continue
            for e in dp[i][j-a[i]]:
                if not dp1[i][j-a[i]][e]:
                    continue
                dp[i+1][j][e+1] += dp[i][j-a[i]][e]
                dp1[i+1][j][e+1] = 1
            if j == s and len(dp[i+1][j]):
                for e in dp[i+1][j]:
                    ans += dp[i+1][j][e]*dp2[n-e]
                    ans %= mod
        for j in range(s-1,-1,-1):
            for e in dp[i][j]:
                dp[i+1][j][e] += dp[i][j][e]
                dp1[i+1][j][e] = 1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import copy
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 = [None]*(S+1)
    DP[0] = [0]
    DP_new = copy.deepcopy(DP)
    for i in range(1, N+1):
        for wa in range(S+1):
            if 0 <= wa-A[i-1] <= S:
                if DP[wa-A[i-1]] is not None:
                    if DP_new[wa] is None:
                        DP_new[wa] = [(k+1) % MOD for k in DP[wa-A[i-1]]]
                    else:
                        DP_new[wa] += [(k+1) % MOD for k in DP[wa-A[i-1]]]
        DP = copy.deepcopy(DP_new)
        # print(DP)

    # 組み合わせはDP[N][S]個存在する。
    # DPを逆に辿って集合を得る
    # 集合を含むような部分集合を数えあげる
    ans = 0
    if DP[-1] is None:
        print(0)
        return
    for s in DP[-1]:
        ans += pow(2, N - s, MOD)
        ans %= MOD
    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

class combnk_mod(object):
    # pが素数かつaとpが互いに素であるとき
    # フェルマーの小定理より以下が成り立つ.
    # 1 / a = a ** (p - 2) (mod p)
    # これを使って (1 / k!) mod p を計算する.
    def __init__(self, maxn, p):
        self.maxn = maxn
        self.p = p
        self.x = [1] # 分母にあたる数 1 / n! mod p
        self.y = [1] # 分子にあたる数. n! mod p
        for i in range(1, self.maxn + 1):
            self.x.append(self.x[-1] * pow(i, self.p - 2, self.p) % self.p)
            self.y.append(self.y[-1] * i % self.p)

    def combnk(self, n, k):
        if n < k:
            return 0
        return (self.x[n - k] * self.x[k] * self.y[n]) % self.p

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

C = combnk_mod(n, MOD)

X = [([0], s)]
y = defaultdict(int)
for ai in a:
    Xi = []
    for l, r in X:
        if r < ai:
            continue
        Xi.append((l, r))
        if r == ai:
            y[len(l)] += 1
            continue
        elif r - ai >= ai:
            Xi.append((l + [ai], r - ai))
    X = Xi

ans = 0
for k, v in y.items():
    for i in range(k, n + 1):
        ans += v * C.combnk(n - k, i - k) % MOD
        ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

print(dp[n][s])

Submission status: Time Limit Exceeded

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



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

cnt=0
Li = [int(a) for a in input().split()]
Li = np.array(Li)

for i in range(1, n+1):
    T_gun = np.array(list(itertools.combinations(Li, i)))
    seki = T_gun.sum(axis=1)
    cnt += sum(seki == s) * 2**(n-i)
    if cnt >= 998244353:
        cnt = cnt % 998244353

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
def part_sum(a,A):
  
  #初期化
  N=len(a)
  dp=[[[0 for i in range(N+1)] for i in range(A+1)] for j in range(N+1)]
  dp[0][0][0]=1

  #DP
  for i in range(N):
    for j in range(A+1):
      for k in range(N):
        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]% MOD
        else: #入る可能性はない
            dp[i+1][j][k]=dp[i][j][k]%MOD
  return dp[N][A]



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

ans = 0
sm = part_sum(A,S)
for n in range(N+1):
    p = pow(2,N-n,MOD)
    ans += p*sm[n]
    ans %= MOD
print (ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
from itertools import groupby, accumulate, product, permutations, combinations
N, S = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
from collections import deque
cum = list(accumulate(A))[::-1]
A = A[::-1]
d = deque([(0,0,0)])
i = 0
lis = [0]*(N+1)
while len(d):
    a,cnt,i = d.popleft()
    if a+A[i]==S:
        lis[cnt+1] += 1
    elif a+cum[i]>=S and a+A[i]<S:
        d.append((a+A[i],cnt+1,i+1))
    if i<N-1 and cum[i+1]>=S-a:
        d.append((a,cnt,i+1))
ans = 0
for i in range(1,N+1):
    ans += lis[i]*pow(2,N-i,mod)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC169 F Knapsack for All Subsets

from collections import deque
from collections import Counter

def merge_dict_add_values(d1, d2):
    return dict(Counter(d1) + Counter(d2))

n, s = map(int, input().split())
a_dq = deque([int(x) for x in input().split()])

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

for i in range(n):
    _tmp = a_dq.popleft()
    for j in range(s+1):
        if j-_tmp < 0:
            dp[i+1][j] = dp[i][j]
        else:
            _tmp_d = dp[i][j-_tmp]
            _dict = dict()
            for k in _tmp_d.keys():
                _dict[k+1] = _tmp_d[k]
            dp[i+1][j] = merge_dict_add_values(dp[i][j],_dict)

# print(dp[n][s])
ans = 0
for k in dp[n][s].keys():
    v = dp[n][s][k]
    ans += (2**(n-k)) * v
    
print(ans%998244353)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def combnk_mod(n, k, p):
    # pが素数かつaとpが互いに素であるとき
    # フェルマーの小定理より以下が成り立つ.
    # 1 / a = a ** (p - 2) (mod p)
    # これを使って (1 / k!) mod p を計算する.

    if  2 * k > n:
        k = n - k
    x = 1 # 分母にあたる数 1 / n! mod p
    y = 1 # 分子にあたる数. n! / (n - k)! mod p
    for i in range(1, k + 1):
        x *= pow(i, p - 2, p)
        y *= n - i + 1
        x %= p
        y %= p
    return (x * y) % p

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

X = [([0], s)]
y = defaultdict(int)
for ai in a:
    Xi = []
    for l, r in X:
        if r < ai:
            continue
        Xi.append((l, r))
        if r == ai:
            y[len(l)] += 1
            continue
        elif r - ai >= ai:
            Xi.append((l + [ai], r - ai))
    X = Xi

ans = 0
for k, v in y.items():
    for i in range(k, n + 1):
        ans += v * combnk_mod(n - k, i - k, MOD) % MOD
        ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

dp = [[] for _ in range(N + 1)]
dp[0] = [[0, 0]]
bef_dp = dp[0]
ans = 0
for i in range(1, N + 1):
    now_A = A_list[i - 1]
    bef_dp = dp[i - 1]
    for j in range(len(bef_dp)):
        num_num, num_sum = bef_dp[j]
        # print(i, num_sum, now_A)
        if num_sum + now_A == S:
                ans = (ans + 2 ** (N - (num_num + 1))) % 998244353
        elif num_sum + now_A < S:
                dp[i].append([num_num + 1, num_sum + now_A])
        dp[i].append([num_num, num_sum])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, copy
# import numpy as np
# import scipy
from collections import defaultdict
input = sys.stdin.readline
mod = 998244353
def main():
    n,s = map(int,input().split())
    a = list(map(int, input().split()))
    dp = [[defaultdict(int) for _ in range(s+1)] for _ in range(n+1)]
    dp1 = [[defaultdict(int) for _ in range(s+1)] for _ in range(n+1)]
    dp[0][0][0] = 1
    dp1[0][0][0] = 1
    ans = 0
    for i in range(n):
        for j in range(s,-1,-1):
            if j-a[i] < 0:
                continue
            if not dp1[i][j-a[i]]:
                continue
            for e in dp[i][j-a[i]]:
                if not dp1[i][j-a[i]][e]:
                    continue
                dp[i+1][j][e+1] += dp[i][j-a[i]][e]
                dp1[i+1][j][e+1] = 1
            if j == s and len(dp[i+1][j]):
                for e in dp[i+1][j]:
                    ans += dp[i+1][j][e]*pow(2,n-e,mod)
                    ans %= mod
        for j in range(s-1,-1,-1):
            for e in dp[i][j]:
                dp[i+1][j][e] += dp[i][j][e]
                dp1[i+1][j][e] = 1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

DP = np.zeros((N+1, S+1), dtype=np.int64)#[[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]:
      DP[i + 1][j] = (DP[i][j] * 2 + DP[i][j - A[i]]) % MOD
    else:
      DP[i + 1][j] = (DP[i][j] * 2) % MOD
print(DP[-1][-1] % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

N,S = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
P = []

def BFS(now,i,pattern):
    if now == S:
        P.append(pattern)
    else:
        if i < N:
            if now + A[i] <= S:
                BFS(now+A[i],i+1,pattern+1)

            BFS(now,i+1,pattern)

BFS(0,0,0)

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


ans = 0
n = len(P)
for i in range(n):
    l = P[i]
    ans += pow_2[N-l]
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
mod = 998244353

def solve():
    input = sys.stdin.readline
    N, S = map(int, input().split())
    A = [int(a) for a in input().split()]
    DP = [[0 for _ in range(S + 1)] for i in range(N)]
    DP[0][0] = 2
    if A[0] <= S: DP[0][A[0]] = 1
    ans = 0
    for i, a in enumerate(A[1:]):
        for s in range(S + 1):
            if DP[i][s] > 0:
                DP[i+1][s] += (DP[i][s] * 2) % mod
                DP[i+1][s] %= mod
                if s + a <= S:
                    DP[i+1][s+a] += DP[i][s]
                    DP[i+1][s+a] %= mod         
    print(DP[N-1][S])
    #print(DP)

    return 0

if __name__ == "__main__":
    solve()

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:
            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:
                ans.append(1)
            else:
                if n-1 >= 0 and DP[n-1][wa-A[n-1]] != 0:
                    b = reconstruct(n-1, wa-A[n-1])
                    ans.extend([bb+1 for bb in b])
        return ans

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

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

print(dp[N][S])

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, copy
# import numpy as np
# import scipy
from collections import defaultdict
input = sys.stdin.readline
mod = 998244353
def main():
    n,s = map(int,input().split())
    a = list(map(int, input().split()))
    dp = [[defaultdict(int) for _ in range(s+1)] for _ in range(n+1)]
    dp[0][0][0] = 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 e in dp[i][j-a[i]]:
                if not dp[i][j-a[i]][e]:
                    continue
                dp[i+1][j][e+1] += dp[i][j-a[i]][e]
            if j == s and len(dp[i+1][j]):
                for e in dp[i+1][j]:
                    ans += dp[i+1][j][e]*pow(2,n-e,mod)
                    ans %= mod
        for j in range(s-1,-1,-1):
            for e in dp[i][j]:
                dp[i+1][j][e] += dp[i][j][e]
    print(ans)
if __name__ == "__main__":
    main()