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,m= map(int, input().split())
a= list(map(int, input().split()))
a.sort()
mod=998244353

def get_integral_value_combination(list, target):
    def a(idx, l, r, t):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(list)):
            a((u + 1), l + [list[u]], r, t)
        return r
    return a(0, [], [], target)

x=get_integral_value_combination(a, m)

ans=0
for i in range(len(x)):
    ans+=pow(2,(n-len(x[i])))
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from collections import defaultdict


def main():
    n, s = [int(x) for x in input().split()]
    mod = 998244353
    array = [int(x) for x in input().split()]
    index = [x for x in range(n)]
    cnt = defaultdict(int)
    for r in range(1, n + 1):
        for ids in combinations(index, r):
            if sum(array[i] for i in ids) == s:
                cnt[len(ids)] += 1
    ans = 0
    for length, count in cnt.items():
        ans += pow(2, n - length, mod) * count
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

Pre = [[Counter() for _ in range(S+1)] for _ in range(N+1)]

Pre[0][0][0] = 1

for i, a in enumerate(A):
    for j in range(S+1):
        if len(Pre[i][j]) > 0:
            Pre[i + 1][j] += Pre[i][j]
        if a + j <= S:
            for key, value in Pre[i][j].items():
                Pre[i + 1][j + a][key + 1] += value
ans = 0
for key, value in Pre[N][S].items():
    ans += pow(2, N - key, mod) * value
    ans %= mod

print(ans % mod)

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)
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
        for j in range(n):
            dp[n-j] += np.append(np.zeros(ai,dtype=int),dp[n-j-1][:s+1-ai])
        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:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,s=map(int,input().split())
A=[int(i) for i in input().split()]
import collections
import copy
mod=998244353
P=[0]*(n+1)
P[0]=1
for i in range(n):
  P[i+1]=(P[i]*2)%mod
D=collections.defaultdict(list)
D[0].append((0,1))
ans=0
for i,a in enumerate(A):
  DD=copy.deepcopy(D)
  if len(D[s-a]):
    for x,y in D[s-a]:
      ans+=y*P[n-x-1]
      if ans>mod:
        ans%=mod
  for d in D.keys():
    for x,y in D[d]:
      if d+a<=s:
        DD[d+a].append((x+1,1))
  D=DD
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 998244353  # type: int


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

    # 和が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]]
    # 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
        ans += 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")
                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):
        # print(s)
        # print(s, [A[i] for i in s])
        ans += pow(2, N - len(s), MOD)
        # print(2**(N - len(s)))
        ans %= MOD
    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n, s = map(int, input().split())
A = sorted(list(map(int, input().split())))
right_pairs = [0] * (n + 1)
for num_comb in range(1, n+1):
    for group in combinations(A, num_comb):
        if sum(group) == s:
            right_pairs[num_comb] += 1
#print(right_pairs)

def comb(n,k,p):
    """power_funcを用いて(nCk) mod p を求める"""
    from math import factorial
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    a=factorial(n) %p
    b=factorial(k) %p
    c=factorial(n-k) %p
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
    """a^b mod p を求める"""
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p

counter = 0
mod = 998244353
#print(comb(10, 0, mod))
for layer in range(1, n+1):
    for pointer in range(1, layer+1):
        counter += right_pairs[pointer] * comb(n-pointer, layer-pointer, mod)
        counter %= mod
print(counter % mod)

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp =[[0]*(S+1) for _ in range(N+1)]
for i in range(N+1):
    for j in range(S+1):
        if j ==0:
            dp[i][j] = [0]
        else:
            dp[i][j] = []
for i in range(1, N+1):
    a = A[i-1]
    for j in range(S+1):
        if a<=S:
            if j >= a:
                if dp[i-1][j-a] != []:
                    add = []
                    for k in dp[i-1][j-a]:
                        add.append(k+1)
                    dp[i][j] = add+dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = dp[i-1][j]
ans = 0
sq = [1]
for i in range(N):
    sq.append(sq[-1]*2)
for i in dp[N][S]:
    ans = (ans+sq[N-i])%998244353
print(ans)

Submission status: Time Limit Exceeded

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

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

    mod = 998244353

    dp = [[0]*s for _ in range(n)]

    for i in range(n):
        if a[i]-1 < s:
            dp[i][a[i]-1] += 2**i
            dp[i][a[i]-1] %= mod

    for i in range(n):
        for j in range(s):
            if i != n-1:
                dp[i+1][j] += dp[i][j] * 2
                dp[i+1][j] %= mod
            if i != n-1 and j + a[i+1] < s:
                dp[i+1][j+a[i+1]] += dp[i][j]
                dp[i+1][j+a[i+1]] %= mod

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

mod = 998244353

# find subset =S
def sum_subset(S):
    subsets = [[] for i in range(0, S+1)]
    j = 0
    for i in range(1, S+1):
        # 同じ数字を探す
        if j < N and A[j] == i:
            start = j
            while j < N and A[j] == i:
                j += 1
            end = j-1
            subsets[i].extend([[j] for j in range(start, end+1)])

        # i = a + b となる組み合わせ
        for a in range(1,i):
            b = i-a
            for s_a in subsets[a]:
                for s_b in subsets[i-a]:
                    if len(set(s_a) & set(s_b)) == 0:
                        subsets[i].append(s_a+s_b)

    return subsets[S]

subsets = sum_subset(S)
# 重複を除く
subsets_sets = [tuple(sorted(s)) for s in subsets]
subsets_sets = set(subsets_sets)


score_mod = 0
for subset in subsets_sets:
    score_mod = (score_mod+pow(2,N-len(subset)))%mod

print(score_mod)

Submission status: Time Limit Exceeded

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=[defaultdict(int) for _ in range(s+1)]
    dp[0][0]=1
    for k,a in enumerate(aa):
        for i in range(s-a,-1,-1):
            if len(dp[i])==0:continue
            for ln,c in dp[i].items():
                dp[i+a][ln+1]=(dp[i+a][ln+1]+c)%md
        #print(k,dp)
    ans=0
    for ln,c in dp[s].items():
        ans=(ans+pow(2,n-ln,md)*c)%md
    print(ans)

main()

Submission status: Time Limit Exceeded

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

Solution code:
from collections import defaultdict, deque
from math import factorial


def nCr(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)


MOD = 998244353

N, S = map(int, input().split())
A = sorted(map(int, input().split()))
A = [a for a in A if a <= S]

nums = defaultdict(int)
for a in A:
    nums[a] += 1

values = sorted(nums.keys())
queue = deque()
queue.append((0, S, 1, 0))
ans = 0
while queue:
    i, left, total, used = queue.popleft()
    if left == 0:
        ans = (ans + total * pow(2, N - used)) % MOD
        continue
    if i == len(values):
        continue

    queue.append((i + 1, left, total, used))

    j = 1
    while j <= nums[values[i]] and values[i] * j <= left:
        t = total * nCr(nums[values[i]], j) % MOD
        queue.append((i + 1, left - values[i] * j, t, used + j))
        j += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
n,s=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
ans=0
dp=[[[0 for _ in range(s+1)] for _ in range(n+1)] for _ in range(n+1)]
for i in range(n+1):
    dp[i][0][0]=1

for i in range(n):
    for k in range(1,i+2):
        for c in range(1,s+1):
            if c>=A[i]:
                dp[i+1][k][c]=dp[i][k][c]+dp[i][k-1][c-A[i]]
            else:
                dp[i+1][k][c]=dp[i][k][c]

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

Submission status: Time Limit Exceeded

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

ct = Counter()
ct[(0, 0)] = 1
for a in As:
    for (c, v), n in list(ct.items()):
        if v+a <= S:
            ct[(c+1, v+a)] += n

ans = 0
MOD = 998244353
for (c, v), n in ct.items():
    if v == S:
        ans += n * pow(2, (N-c), MOD)
        ans %= MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit

setrecursionlimit(200000)

mod = 998244353

def modpow(m,n):
    b = 1
    p = m
    for k,v in enumerate(format(n,'b')[::-1]):
        if k:
            p = (p * p)%mod
        if v == '1':
            b *= p
            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]

ans = 0

keiro = 0
def rec(i,j):
    global keiro,DP,ans
    if DP[i][j] == 0:
        return
    if i == 0:
        #print(keiro)
        ans += modpow(2,N-keiro)
        ans %= mod
        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)

print(ans)

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)

    
    n, s = mi()
    L = lmi()
    dp = [Counter() 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]] += Counter({1: 1})
            elif j + L[i] <= s and dp[j]:
                dp[j + L[i]] += my_update(dp[j])    # counter
        # print(dp)
    
    ans = 0
    for chain_len, num in dp[s].items():
        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.buffer.readline

n, s = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [[{} for _ in range(s + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
kiroku = [0] * (n)

for i in range(n):
    ni = i + 1
    for j in range(s + 1):
        nj = j
        if dp[i][j] == {}:
            continue
        for key, val in dp[i][j].items():
            if key in dp[ni][nj]:
                dp[ni][nj][key] += val
            else:
                dp[ni][nj][key] = val
        nj = j + A[i]
        if nj <= s:
            for key, val in dp[i][j].items():
                if key + 1 in dp[ni][nj]:
                    dp[ni][nj][key + 1] += val
                else:
                    dp[ni][nj][key + 1] = val
ans = 0
for key, val in dp[n][s].items():
    if key == 0:
        continue
    ans += pow(2, n - key) * val
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

# DP-table : [#Ele.][Sum]
dp = [[0 for j in range(S+1)] for i in range(N+1)]

#Initialize:
dp[0][0] = 1

for i in range(N):#Each A[i]
  temp = [[0 for k in range(S+1)] for j in range(N+1)]
  #Pick A[i]
  for j in range(i+1):
    for k in range(S+1):
      if k + A[i] <= S:
        temp[j+1][k + A[i]] += dp[j][k]

  for j in range(i+2):
    for k in range(S+1):
        dp[j][k] += temp[j][k]
        

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

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % mod
        x *= x % mod
        n //= 2

    return K * x % mod

pow2 = [1] * (n + 1)
for i in range(n):
    pow2[i + 1] = pow2[i] * 2 % mod
inv2 = pow_k(2, mod - 2)

dp[0][0] = pow2[n]
for i in range(1, n + 1):
    for j in range(s + 1):
        if j >= a[i - 1]:
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - a[i - 1]] * inv2 % mod) % mod
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[n][s])

Submission status: Time Limit Exceeded

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

print(dp[n][s])

Submission status: Time Limit Exceeded

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

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

dp[0][0] = 1

for i in range(N):
    for j in range(S, -1, -1):
        for k in range(i, -1, -1):
            if j + A[i] < S + 1:
                dp[j + A[i]][k + 1] += dp[j][k]

tres = dp[S]


res = 0
for i in range(N + 1):
    res += tres[i] * pow(2, N - i, MOD)
    res %= MOD
print(res)

Submission status: Time Limit Exceeded

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

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

mod=998244353

DP=[0]*(S+1)
DP[0]=pow(2,N,mod)

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

for a in A:
    for i in range(S-a,-1,-1):
        DP[i+a]=(DP[i]*INV+DP[i+a])%mod
        
print(DP[S])

Submission status: Time Limit Exceeded

Solution code:
n,s=map(int,input().split())
dp=[0]*(s+1)
mod=998244353
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]*pow(2,mod-2,mod))%mod
print(dp[s])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

LI = lambda: list(map(int, sys.stdin.readline().rstrip().split()))

def main():
    n, s = LI()
    a = LI()
    dp = np.zeros((n+1, s+1), dtype=np.int)
    dp[0][0] = 1

    for i in range(n):
        for w in range(s+1):
            dp[i+1][w] = 2*dp[i][w]
            if w >= a[i]:
                dp[i+1][w] += dp[i][w-a[i]]
            dp[i+1][w] %= 998244353

    print(dp[n][s])

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

B = [0]*(S+1)
B[0] = 1

for a in A:
    C = list(map(lambda x:x*2%MOD, B))
    for i in range(S-a+1):
        C[i+a] = (C[i+a] + B[i])%MOD

    B = C

print(B[-1])

Submission status: Time Limit Exceeded

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

MOD = 998244353

A.sort()
s = 0
for idx, a in enumerate(A):
    s += a
    if s > S:
        break
idx += 1

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

for i in range(N):
    a = A[i]
    for j in range(S - a, -1, -1):
        for k in range(min(idx, i), -1, -1):
            here = dp[j][k]
            if j + a <= S and k + 1 <= idx:
                dp[j + a][k + 1] += here

cnt = 0
K = dp[-1]
for i, c in enumerate(K):
    cnt += c * (pow(2, N - i, MOD))
    cnt %= MOD

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N,S=map(int,input().split())
A=list(map(int,input().split()))
dp=[[0 for i in range(S+1)]for j in range(N+1)]
dp[0][0]=1
for i in range(N):
    for j in range(S+1):
        if j-A[i]>=0:
            dp[i+1][j]+=dp[i][j-A[i]]+dp[i][j]+dp[i][j]
        else:
            dp[i+1][j]+=dp[i][j]+dp[i][j]
print(dp[N][S]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def y():
  n,s = map(int,input().split())
  a = list(map(int,input().split()))
  x = [{} for _ in range(s+1)]
  x[0][0] = 1
  for i in range(n):
    ai = a[i]
    for j in range(s-ai,-1,-1):
      if x[j]:
        for k,v in x[j].items():
          if k+1 in x[j+ai]:
            x[j+ai][k+1] += v
          else:
            x[j+ai][k+1] = v
  c = 0
  mod = 998244353
  def p(n):
    ans = 1
    x = 2
    while n:
      if n % 2:
        ans = (ans*x)%mod
      x *= x
      n >>= 1
    return ans%mod
  for k,v in x[s].items():
    c =  (c +(v*p(n-k)))%mod
  print(c)
y()