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
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def main():
    MOD = 998244353
    N, S = inpl()
    A = sorted(inpl())
    dp = [{} for _ in range(N + 1)]
    dp[0][0] = 1
    for i, a in enumerate(A):
        for j in range(min(S - a, i), -1, -1):
            for k, v in dp[j].items():
                if k + a > S:
                    continue
                if k + a not in dp[j + 1]:
                    dp[j + 1][k + a] = v
                else:
                    dp[j + 1][k + a] = v + dp[j + 1][k + a]
    # print(dp)

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

    ans = 0
    for i in range(1, N + 1):
        if S in dp[i]:
            ans = (ans + dp[i][S] * p2[N - i]) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 998244353
    ans = 0
    dp = [defaultdict(int) 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():
                dp[j + i][k + 1] += v
    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:
# -*- 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(list)
dic[0] = [0]

for a in A:
  dicb = copy.deepcopy(list(dic.items()))
  for s,nl in dicb:
    if s+a <= S:
      for n in nl:
        dic[s+a].append(n+1)

ans = 0
for n in dic[S]:
  ans += pow(2,N-n,998244353)
  ans %= 998244353
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as fac
from functools import lru_cache
import sys
from operator import *
from functools import *
from itertools import *

sys.setrecursionlimit(100000)

n, s = map(int, input().split())
l = [int(i)for i in input().split()]
l.sort(reverse=True)
cum = list(accumulate(l[::-1], add))[::-1] + [0]
# print(cum)
mod = 998244353


@lru_cache(None)
def f(i, tot, nn):
    if cum[i] + tot < s:
        return 0
    elif tot == s:
        return (1 << n - nn) % mod
    else:
        z = 0
        for j in range(n - 1, i - 1, -1):
            newt = tot + l[j]
            if newt <= s:
                z = (z + f(j + 1, newt, nn + 1)) % mod
        return z


print(f(0, 0, 0) % mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62

MOD = 998244353  # type: int
import numpy as np


def s(A, S, ruiseki, N):
    d = dict()
    d[0, 0] = 1  # left:vale right:count
    for i, a in enumerate(A):
        for (left, right) in sorted(d.keys(), reverse=True):
            if left + a > S:
                continue
            if left + ruiseki[N - i] < S:
                break
            if (left + a, right + 1) in d:
                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]"):
    A.sort(reverse=True)
    ruiseki = [0]
    for a in A[::-1]:
        ruiseki.append(ruiseki[-1] + a)
    d = s(np.array(A), S, np.array(ruiseki), N)
    ans = 0
    for val, count in d.keys():
        if val != S:
            continue
        ans += d[val, 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:
# coding: utf-8
import sys
import numpy as np

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

MOD = 998244353
N, S = lr()
A = lr()
dp = np.zeros((N+1, S+1), np.int32)  # dp[i][j]はi個選んだ合計jの個数
dp[0][0] = 1
for a in A:
    for i in range(N-1, -1, -1):
        dp[i+1][a:] += dp[i][:-a]

dpS = dp[:, S]
answer = 0
power = 1
for x in dpS[1:][::-1]:
    answer += power * x
    answer %= MOD
    power *= 2; power %= MOD
print(answer%MOD)

Submission status: Time Limit Exceeded

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

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(list)
dic[0] = [0]

for a in A:
  dicb = copy.deepcopy(list(dic.items()))
  for s,nl in dicb:
    if s+a <= S:
      for n in nl[::-1]:
        dic[s+a].append(n+1)

ans = 0
for n in dic[S]:
  ans += pow(2,N-n,998244353)
  ans %= 998244353
print(ans)

Submission status: Time Limit Exceeded

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

from collections import defaultdict
dp = defaultdict(lambda: 0)
dp[0] = 1
B = 10000
for a in A:
    for k,v in list(dp.items()):
        if k%B + a > S: continue
        dp[k+a+B] += v

ans = 0
for k,v in dp.items():
    if k%B!=S: continue
    i = k//B
    ans += pow(2,N-i,MOD) * v
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

sys.setrecursionlimit(10**7)

n, s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0 for __ in range(n+1)] for _ in range(s+1)]
dp[0][0] = 1
index = [(0, 0)]
for i in range(n):
    _index = []
    for j, k in index:
        if j+a[i] <= s:
            dp[j+a[i]][k+1] += 1
            _index.append((j+a[i], k+1))
    index = index + _index

ans = 0
for i in range(n+1):
    if dp[s][i] != 0:
        ans += dp[s][i]*2**(n-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 = [[[] for i in range(S+1)] for i in range(N+1)]
dp[0][0].append(0)
for i in range(1,N+1):
    a = A[i-1]
    for j in range(S-a+1):
        if len(dp[i-1][j]) != 0:
            for k in dp[i-1][j]:
                dp[i][j+a].append(k+1)
    for j in range(S+1):
        if len(dp[i-1][j]) != 0:
            for k in dp[i-1][j]:
                dp[i][j].append(k)
A = dp[N][S]
A.sort()
ans = 0
mod = 998244353
for a in A:
    x = N - a
    ans += 2**x % mod
    ans = ans % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(5000)

MOD = 998244353  # type: int

cache = [[None] * (3000+1) for _ in range(3000+1)]

def f(s, i, A, N):
    if s < 0:
        return 0
    if i == N:
        if s == 0:
            return 1
        return 0
    if cache[i][s] is not None:
        return cache[i][s]
    ret = (2 * f(s, i+1, A, N) % MOD + f(s-A[i], i+1, A, N)) % MOD
    cache[i][s] = ret
    return ret

def solve(N: int, S: int, A: "List[int]"):
    return f(S, 0, A, N)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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]"
    print(solve(N, S, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Time Limit Exceeded

Solution code:
from __future__ import division, print_function

''' Hey stalker :) '''
INF = 10 ** 10
TEST_CASES = False

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



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

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


class FastIO(IOBase):
    newlines = 0

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

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

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

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


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


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


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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

n , s = map(int, input().split())
a = list(map(int,input().split()))
x=[]
y=[0]*(n+1)
N = 998244353

def dfs(now,sum):
    if sum == s:
        z=y.copy()
        x.append(z)
        return
    if now == n:
        return

    for i in range(2):
        if i==0:
            dfs(now+1,sum)
        if i==1:
            y[now]=1
            sum+=a[now]
            dfs(now+1,sum)
            y[now]=0
            sum-=a[now]

dfs(0,0)

ans = 0
for i in x:
    ans += pow(2,n-sum(i),N)
ans %= N
print(ans)

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(300000)

MOD = 998244353  # type: int

def calc_fraction_mod(numerator, denominator):
    '''
        returns numerator / denominator (mod MOD)
    '''
    inv = pow(denominator, MOD - 2, MOD)
    return numerator * inv % MOD


def solve(N: int, S: int, A: "List[int]"):
    dp = [0] * (S + 1)
    dp[0] = pow(2, N, MOD)
    for a in A:
        for s in range(S + 1)[::-1]:
            if dp[s] == 0:
                continue
            if s + a <= S:
                dp[s + a] += calc_fraction_mod(dp[s], 2)
                dp[s + a] %= MOD
    print(dp[S] % MOD)
    #ret = 0
    #print(ret)

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:
N,S = map(int,input().split())
A = list(map(int,input().split()))
MOD = 998244353

from collections import defaultdict
dp = defaultdict(lambda: 0)
dp[0] = 1
B = 10000
for a in A:
    for k,v in list(dp.items()):
        if k%B + a > S: continue
        dp[k+a+B] += v

ans = 0
for k,v in dp.items():
    if k%B!=S: continue
    i = k//B
    ans += pow(2,N-i,MOD) * v
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
def productall(a):
    N = len(a)
    if N == 0: return [1]
    A = [1] * N + a[:]
    mad = 3030
    pa1 = (1 << k * 4 + 16) - ((1 << k * 4 + 16) % P)
    pa2 = (1 << k * 2 + 24) - ((1 << k * 2 + 24) % P)
    pa3 = (1 << k + 28) - ((1 << k + 28) % P)
    m1 = int(("1" * (k * 4 - 16) + "0" * (k * 4 + 16)) * mad, 2)
    m2 = int(("1" * (k * 6 - 24) + "0" * (k * 2 + 24)) * mad, 2)
    m3 = int(("1" * (k * 7 - 28) + "0" * (k + 28)) * mad, 2)
    m = int("1" * (k * 8) * mad, 2)
    def modP(x):
        x &= m
        x -= ((x & m1) >> k * 4 + 16) * pa1
        x -= ((x & m2) >> k * 2 + 24) * pa2
        x -= ((x & m3) >> k + 28) * pa3
        return x
 
    for i in range(N)[::-1]:
        A[i] = modP(A[2*i] * A[2*i+1])
 
    t = "0" * K * S + bin(A[1])[2:] + "_"
    return [int(t[-(i+1) * K - 1:-i * K - 1], 2) % P for i in range((len(t)+K-2) // K)][S]

P = 998244353
k = 12
K = k * 8
N, S = map(int, input().split())
A = [(1 << K * int(a)) + 2 for a in input().split()]
print(productall(A) % P)

Submission status: Time Limit Exceeded

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

p = [1]
for i in range(N+1):
  p.append(p[-1] * 2 % MOD)

ans = 0
for i in range(1, N+1):
  k = [ sum(j) for j in combinations(A, i)]
  #print(k.count(S), p[N-i])
  ans += k.count(S) * p[N-i] % MOD

print(ans)

Submission status: Time Limit Exceeded

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

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

fac_inv2 = pow(2,MOD-2,MOD)

for i in range(n):
    if a[i]<=s:
        dp[i+1][a[i]-1] = dp[i][a[i]-1] + 1
    for j in range(min(a[i]-1,s)):
        dp[i+1][j] = dp[i][j]
    for j in range(s-a[i]):
        dp[i+1][j+a[i]] = dp[i][j+a[i]] + (dp[i][j] * fac_inv2) %MOD
        dp[i+1][j+a[i]] %= MOD

ans = dp[-1][-1]

ans *= pow(2,n-1,MOD)
ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

MOD = 998244353
N, S = lr()
A = lr()
dp = np.zeros((N+1, S+1), np.int32)
dp[0][0] = 1
#dp = np.array([[0] * (S+1) for _ in range(N+1)])  # dp[i][j]はi個選んだ合計jの個数
for a in A:
    for i in range(N-1, -1, -1):
        dp[i+1][a:] += dp[i][:-a]

dpS = dp[:, S]
answer = 0
for i, x in enumerate(dpS):
    answer += pow(2, (N-i), MOD) * x
    answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
L = [[0 for i in range(S+1)] for j in range(N+1)]
L[0][0] = 1
for j, a in enumerate(A):
  for i in range(S+1):
    if i < a:
      L[j+1][i] = (2 * L[j][i]) % mod
    else:
      L[j+1][i] = (2 * L[j][i] + L[j][i-a]) % mod
print(L[N][S])

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod=998244353
    n,s=map(int,input().split())
    A=list(map(int,input().split()))
    DP=[[0]*(s+1) for _ in range(n+1)]
    p=1
    for i in range(n+1):
        DP[i][0]=p
        p*=2
    for i,a in enumerate(A):
        for j in range(1,s+1):
            DP[i+1][j]=DP[i][j]*2
            if j>=a:
                DP[i+1][j]+=DP[i][j-a]
            DP[i+1][j]%=mod
    print(DP[-1][-1])
    #print(DP)
    
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
MOD = 998244353

N, S = map(int, input().split())
A = list(map(int, (input().split())))
dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j]*2
        dp[i+1][j] %= MOD
        if j+A[i] <= S:
            dp[i+1][j+A[i]] += dp[i][j]
            dp[i+1][j+A[i]] %= MOD
print(dp[-1][S])

Submission status: Time Limit Exceeded

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

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

for i in range(n):
    for j in range(s+1):
        for k in dp[i][j].keys():
            if k in dp[i+1][j]:
                dp[i+1][j][k] += dp[i][j][k]
            else:
                dp[i+1][j][k] = dp[i][j][k]

            if j + a[i] <= s:
                if k+1 in dp[i+1][j+a[i]]:
                    dp[i+1][j+a[i]][k+1] += dp[i][j][k]
                else:
                    dp[i+1][j+a[i]][k+1] = dp[i][j][k]


for k in dp[n][s].keys():
    ans = (ans + dp[n][s][k] * pow(2, n-k, mod) % mod) % mod

print(ans)

Submission status: Time Limit Exceeded

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

print(main())

Submission status: Time Limit Exceeded

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

from collections import defaultdict
dp = defaultdict(lambda: 0)
dp[(0,0)] = 1
for a in A:
    for (i,j),v in list(dp.items()):
        if j+a > S: continue
        dp[(i+1,j+a)] += v

ans = 0
for (i,j),v in dp.items():
    if j!=S: continue
    ans += pow(2,N-i,MOD) * v
print(ans%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()))
ans = 0
def bit_all(n,a):
    global ans
    for i in range(2 ** n):
        check = 0
        num = 0
        for j in range(n):
            # 順に右にシフトさせ最下位bitのチェックを行う
            if ((i >> j) & 1):
                check += a[j]
                num += 1
                if check > s:
                    break
        if check == s:
            ans += 2**(n-num)
    print(ans)
bit_all(len(a),a)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62

MOD = 998244353  # type: int


def solve(N: int, S: int, A: "List[int]"):
    d = collections.defaultdict(int)
    d[0, 0] = 1  # left:vale right:count
    A.sort(reverse=True)
    ruiseki = [0]
    for a in reversed(A):
        ruiseki.append(ruiseki[-1] + a)
    for i, a in enumerate(A):
        for (left, right) in sorted(d.keys(), reverse=True):
            if left + a > S:
                continue
            if left + ruiseki[N-i] < S:
                break
            if (left + a, right + 1) in d:
                d[left + a, right + 1] += d[left, right]
            else:
                d[left + a, right + 1] = d[left, right]

    ans = 0
    for val, count in d.keys():
        if val != S:
            continue
        ans += d[val, count] * 2 ** (N - count)
        ans %= 998244353
    print(ans)


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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
mod = 998244353

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

pts = []
for x in nums:
	for pt in copy.deepcopy(pts):
		if pt[1] + x <= s:
			pts.append([pt[0] + 1, pt[1] + x])
	pts.append([1, x])
pts = [pt[0] for pt in pts if pt[1] == s]

ans = 0
for pt in pts:
	ans = ans + pow(2, n - pt, mod)
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(5000)

MOD = 998244353  # type: int

def gen_f(N, A, S):
    cache = [[None] * (S+1) for _ in range(N+1)]
    def f(s, i):
        if s < 0:
            return 0
        if i == N:
            if s == 0:
                return 1
            return 0
        if cache[i][s] is not None:
            return cache[i][s]
        ret = (2 * f(s, i+1) % MOD + f(s-A[i], i+1)) % MOD
        cache[i][s] = ret
        return ret
    return f

def solve(N: int, S: int, A: "List[int]"):
    f = gen_f(N, A, S)
    return f(S, 0)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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]"
    print(solve(N, S, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    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 j in range(s+1)] for i in range(n)]
dp[0][0]=2
if a[0]<=s: dp[0][a[0]]=1

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

Submission status: Time Limit Exceeded

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

N,S, *A = map(int, sys.stdin.buffer.read().split())
mod = 998244353

answer = [0 for _ in range(S+1)]
power2 = 1

for j in range(N):
  a = A[j]
  answer_next = [(2*answer[i])%mod for i in range(S+1)]
  if a<=S:
    answer_next[a] = (answer_next[a]+power2)%mod
    for i in range(a+1,S+1):
      answer_next[i] = (answer_next[i]+answer[i-a])%mod
  answer = answer_next
  power2 = (2*power2)%mod

print(answer[S])