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


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


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


ans = 0


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

    def dfs(n, s, ret):

        global ans

        if s == 0:
            ans = (ans + pow(2, N - ret)) % mod
            return
        if n == 0:
            return

        if sum(A[:n]) < s:
            return

        dfs(n - 1, s - A[n - 1], ret + 1)

        dfs(n - 1, s, ret)

    dfs(N, S, 0)

    print(ans)


if __name__ == "__main__":
    main()

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 and 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]
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])
print(ans%998244353)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 998244353
    dp = [dict() for _ in range(s + 1)]
    dp[0][0] = 1
    for i in a:
        for j in range(s - i, -1, -1):
            for k, v in dp[j].items():
                if k + 1 in dp[j + i]:
                    dp[j + i][k + 1] += v
                else:
                    dp[j + i][k + 1] = v
    ans = 0
    for k, v in dp[-1].items():
        ans += pow(2, n - k, mod) * v
    ans %= mod
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
# input()
# int(input())
# map(int,input().split())
# list(map(int,input().split()))
# [input() for _ in range(n)]

import copy

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

sa = sorted(a)

nums = [[] for _ in range(s+1)]
for i in range(n):
  nn = copy.deepcopy(nums)
  #print("nn: {}".format(nn))
  for j in range(s+1):
    for k in range(len(nn[j])):
      #print(j)
      #print(sa[i])
      #print(k)
      if j+sa[i]<=s:
        nums[j+sa[i]].append(nn[j][k]+1)
  if sa[i]<=s:
    nums[sa[i]].append(1)

  #print(nums)

ans = 0
for v in nums[s]:
  ans += 2**(n-v)
  ans = ans%998244353

print(ans)

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]"):
    d1 = s(A[:N // 2], S, N)
    d2 = s(A[N // 2:], S, N)

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

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


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, S, (A))


if __name__ == '__main__':
    main()

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


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


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


ans = 0


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

    def dfs(n, s, ret):

        global ans

        if s == 0:
            ans = (ans + pow(2, N - ret)) % mod
            return
        if n == 0:
            return

        if sum(A[:n]) < s:
            return

        dfs(n - 1, s - A[n - 1], ret + 1)

        dfs(n - 1, s, ret)

    dfs(N, S, 0)

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

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 i in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
    for j in range(n, 0, -1):
        for k in range(s, -1, -1):
            if k >= a[i-1]:
                dp[j][k] = (dp[j-1][k-a[i-1]] + dp[j][k]) % mod
            else:
                dp[j][k] = dp[j][k]
dp2 = [dp[i][s] for i in range(n + 1)]
ans = 0
for i in range(n + 1):
    temp = dp2[i] * pow(2, n - i, mod)
    ans += temp
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
MAX = 3010


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


INV = [1] * (MAX+1)
INV[MAX] = div(1, pow(2, MAX, MOD))
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * 2) % MOD


def encode(num, total, S):
    return num * (S+1) + total


def decode(val, S):
    return val // (S+1), val % (S+1)


def main():
    N, S = map(int, input().split())
    A = list(sorted(map(int, input().split())))
    prev = [0] * (S+1)
    prev[0] = pow(2, N, MOD)
    for i in range(N):
        cur = list(prev)
        for total in range(S+1):
            if total + A[i] > S:
                continue
#            key = encode(num+1, total + A[i], S)
            cur[total + A[i]] = (cur[total + A[i]] +
                                 prev[total] * div(1, 2)) % MOD
        prev = cur
    print(cur[S])


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:
import itertools
import copy
from collections import deque
import heapq
n,s = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
flag = True
ans = 0
while flag:
    check = 0
    num = 0
    c = True
    for i in a:
        check += i
        num += 1
        if check > s:
            a.pop(0)
            c = False
            if num == 1:
                flag == False
            break
        elif check == s:
            a.pop(0)
            if num == 1:
                flag == False
            break
    if c:
        ans+=2**(n-num)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, S = map(int, input().split())
A = tuple(map(int, input().split()))

mod = 998244353
U = 3000

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

dp = defaultdict(int)
dp[(0, 0)] = 1

cnt = [0] * (U + 1)

tmp = 0
for i, a in enumerate(A):
    newDP = defaultdict(int)
    for (sm, cnt), v in dp.items():
        # 追加しない
        newDP[(sm, cnt)] += v
        newDP[(sm, cnt)] %= mod
        # 追加する
        if sm+a <= S:
            newDP[(sm+a, cnt + 1)] += v
            newDP[(sm+a, cnt + 1)] %= mod
    dp = newDP

ans = 0
for i in range(N + 1):
    ans = (ans + pow2[N - i] * dp[(S, i)]) % mod
print(ans)

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].append(0)
  for i in range(n):
    ai = a[i]
    for j in range(s-ai,-1,-1):
      if x[j]:
        xa = x[j+ai].append
        for xj in x[j]:
          xa(xj+1)
  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 a in x[s]:
    c = (c + p(n-a))%mod
  print(c)
y()

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 = 0
for c in C:
    wa = 0
    for i in c:
        wa += A[i]
    if wa == S:
        for cc in C:
            if set(c) <= set(cc):
                ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)
N, S = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
ind = get_integral_value_combination(A, S)
for i in ind:
    ans += 2 ** (N - len(i))
ans %= 998244353
print(ans)

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])
print(ans%998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
#from collections import frozenset

def main():
    N, S = tuple(int(c) for c in input().split(' '))
    A = [int(c) for c in input().split(' ')]
    A = np.array(A)
    #print(A)

    cnt = 0
    ss = set()
    for mask in itertools.product([False, True], repeat=N):
        AT = A[list(mask)]
        if AT.sum() == S:
            #print(AT)
            s = frozenset(i+1 for i in range(N) if mask[i])
            #print('first', s)
            ss.add(s)
            cnt += 1
        else:
            q = frozenset(i+1 for i in range(N) if mask[i])
            for s in ss:
                if s <= q:
                    #print(s, 'in', q)
                    cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353


def solve(n, s, a_list):
    dp = [[0] * 3001 for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        a = a_list[i]
        for v in range(3001):
            dp[i + 1][v] = (dp[i][v] * 2) % MOD
        for v in range(3001):
            if v + a > 3000:
                break
            dp[i + 1][v + a] = (dp[i + 1][v + a] + dp[i][v]) % MOD
    # print(dp[n])
    return dp[n][s]


def main():
    n, s = map(int, input().split())
    a_list = list(map(int, input().split()))
    res = solve(n, s, a_list)
    print(res)


def test():
    assert solve(3, 4, [2, 2, 4]) == 6
    assert solve(5, 8, [9, 9, 9, 9, 9]) == 0
    assert solve(10, 10, [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]) == 3296


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

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


dp = [[0]*(3001) for i in range(3001)]
memo = [[ [] for j in range(3001)] for i in range(3001)]
dp[0][a[0]]=1
dp[0][0]=1
memo[0][a[0]]=[1]
memo[0][0]=[0]

for i in range(1,n):
    for suma in range(s+1):
        if suma-a[i]>=0:
            dp[i][suma] = dp[i-1][suma]+dp[i-1][suma-a[i]]
            memo[i][suma] = memo[i-1][suma] + [m+1 for m in memo[i-1][suma-a[i]]]
        else:
            dp[i][suma] = dp[i-1][suma]
            memo[i][suma] = memo[i-1][suma] 

print( sum(2**(n-i)%mod for i in memo[n-1][s]) %mod )

Submission status: Time Limit Exceeded

Solution code:
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
import numpy as np
dp=np.zeros((n+1,s+1),int)
# dp[i][j]:aの中からi個選んでjにできるものの個数。
dp[0][0]=1
for ai in a:
  if ai>s:
    continue
  for j in range(n,0,-1):
    dp[j][ai:]+=dp[j-1][:-ai]
    dp[j]%=mod
ans=0
for i in range(n+1):
  ans+=dp[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 = input().split()
count = 0
for i in range(2 ** n):
  bit_list = []
  for j in range(n):
    if i >> j & 1:
      bit_list.append(int(a[j]))
  #print(bit_list, sum(bit_list), s)
  if bit_list != []:
    for p in range(2 ** len(bit_list)):
      subset_list = []
      for q in range(len(bit_list)):
        if p >> q & 1:
          subset_list.append(bit_list[q])
      if subset_list != [] and sum(subset_list) == s:
        count += 1
        count %= 998244353
      #print(bit_list, subset_list, total)
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, s = map(int, input().split())
*A, = map(int, input().split())
p = 998244353
DP = [[0 for j in range(s + 1)] for i in range(n + 1)]
DP[0][0] = 1
for i in range(n):
    for j in range(s + 1):
        if j >= A[i]:
            DP[i + 1][j] = (2 * DP[i][j] + DP[i][j - A[i]]) % p
        else:
            DP[i + 1][j] = (2 * DP[i][j]) % p
print(DP[n][s] % p)

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 = defaultdict(int)
        for sm, cnt in sets:
            #print(sm, cnt, sets)
            if sm+i<=s:
                new[(sm+i, cnt+1, )] += sets[(sm, cnt, )]
        #print(i, new)
        sets[(i, 1,)] += 1
        for i in new:
            sets[i]+=new[i]
    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:
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
import math
import numpy as np
dp=np.zeros((n+1,s+1),int)
# dp[i][j]:aの中からi個選んでjにできるものの個数。
dp[0][0]=1
for ai in a:
  if ai>s:
    continue
  for j in range(n,0,-1):
    dp[j][ai:]+=dp[j-1][:-ai]
ans=0
for i in range(n+1):
  ans+=dp[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()))
k=n
A.sort()
for i in range(n):
    if A[i]>s:
        k=i
        break
del A[k:n]

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

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

print(ans%998244353)

Submission status: Time Limit Exceeded

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


dp = [[0]*(max(s,max(a))+1) for i in range(max(n,max(a)) )]
memo = [[ [] for j in range(max(s,max(a))+1)] for i in range(max(n,max(a)))]
dp[0][a[0]]=1
dp[0][0]=1
memo[0][a[0]]=[1]
memo[0][0]=[0]

for i in range(1,n):
    for suma in range(s+1):
        if suma-a[i]>=0:
            dp[i][suma] = dp[i-1][suma]+dp[i-1][suma-a[i]]
            memo[i][suma] = memo[i-1][suma] + [m+1 for m in memo[i-1][suma-a[i]]]
        else:
            dp[i][suma] = dp[i-1][suma]
            memo[i][suma] = memo[i-1][suma] 

print( sum(2**(n-i)%mod for i in memo[n-1][s]) %mod )

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]
          dp[i][j][k]%=mod
  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:
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(i+1):
                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 = 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)]
dp = [0 for i in range( (S+1)*(N+1) )]

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

for i in range(N):#Each A[i]
  #temp = [[0 for k in range(S+1)] for j in range(N+1)]
  temp = [0 for i in range( (S+1)*(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]
        temp[(j+1)*(S+1) + k + A[i]] += dp[j * (S+1) + k]

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

Submission status: Time Limit Exceeded

Solution code:
n, s = map(int, input().split())
aa = list(map(int, input().split()))
mod = 998244353
states = {(0,0):1}
cnt = 0
for a in aa:
    s_new = {}
    for state, v in zip(states.keys(), states.values()):
        s_new[state] = s_new.get(state,0) + v
        if state[1] + a <s:
            s_new[(state[0]+1, state[1] + a)] = s_new.get((state[0]+1, state[1] + a), 0) + v
        elif state[1] + a == s:
            cnt = (cnt + v*(2**(n-state[0]-1)) )%mod
    states = s_new
print(cnt)

Submission status: Time Limit Exceeded

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

def count_up(hairetu, s, n):
    for j in range(1, n+1):
        global cnt
        t_gun = np.array(list(itertools.combinations(hairetu, j)))
        seki = t_gun.sum(axis=1)
        cnt += sum(seki == s)

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)))
    for t in T_gun:
        count_up(t, s, i)

print(cnt)

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(0)
    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 += 1
                dp[i+1][j].append(x)
            if j == s and len(dp[i+1][j]):
                for e in dp[i+1][j]:
                    ans += pow(2,n-e,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:
def modpow(val, n, mod):
    ret = 1
    while n:
        if n & 1:
            ret = (ret * val) % mod
        val = (val * val) % mod
        n = n >> 1
    return ret


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

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


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

mtx = part_sum(a, s)

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

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

print(ret % 998244353)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 998244353
 
n, s = map(int, input().split())
a = [int(item) for item in input().split()]
# dp[i-th item][j val] : tuple(cnt, used cnt)
dp = [[dict() for _ in range(s+1)] for _ in range(n + 1)]
dp[0][0][0] = 1
 
for i, item in enumerate(a):
    for j in range(s):
        for uc, c in dp[i][j].items():
            if uc not in dp[i+1][j]:
                dp[i+1][j][uc] = c
            else:
                dp[i+1][j][uc] += c
            if j + item > s:
                continue
            if uc + 1 not in dp[i+1][j + item]:
                dp[i+1][j + item][uc + 1] = c
            else:
                dp[i+1][j + item][uc + 1] += c
 
ans = 0
for dics in dp:
    for key, val in dics[-1].items():
        ans += pow(2, n - key, MOD) * val
        ans %= MOD
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 = [[[] for _ in range(S+1)] for _ in range(N+1)]

Pre[0][0] = [0]

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 n in Pre[i][j]:
                    Pre[i + 1][j + a].append(n + 1)
ans = 0
Ans = Counter(Pre[N][S])
for key, value in Ans.items():
    ans += pow(2, N - key, mod) * value
    ans %= mod

print(ans % mod)