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:
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)
U = 3000*3000
dp[(0, 0)] = 1
for a in 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:
def moddiv(a, b, mod):
    inverted_b = pow(b, mod-2, mod)
    return (a*inverted_b) % mod

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)
    for a in A:
        for i in reversed(range(a, S + 1)):
            dp[i] = dp[i] + moddiv(dp[i - a], 2, mod)
    return dp[S] % mod

print(main())

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 = inpl()
    dp = [{} for _ in range(N + 1)]
    dp[0][0] = 1
    for i, a in enumerate(A):
        for j in range(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:
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)
U = 3000*3000
dp[(0, 0)] = 1
for a in A:
    newDP = defaultdict(int)
    for (sm, cnt), v in dp.items():
        # 追加しない
        newDP[(sm, cnt)] += v
        newDP[(sm, cnt)] %= mod
        # 追加する
        if sm+a <= 3000:
            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:
def moddiv(a, b, mod):
    inverted_b = pow(b, mod-2, mod)
    return (a*inverted_b) % mod
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)
    for a in A:
        for i in reversed(range(a, S + 1)):
            dp[i] = (dp[i] + moddiv(dp[i - a], 2, mod)) % mod
    return dp[S]

print(main())

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)
    for a in A:
        for (left, right) in sorted(d.keys(), reverse=True):
            if left + a > S:
                continue
            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:
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
ans = 0
for a in A:
    newDP = defaultdict(int)
    for (sm, cnt), v in dp.items():
        # 追加しない
        newDP[(sm, cnt)] += v
        newDP[(sm, cnt)] %= mod
        # 追加する
        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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(5000)

MOD = 998244353  # type: int

def gen_f(N, A):
    cache = {}
    def f(s, i):
        if (s, i) in cache:
            return cache[(s, i)]
        if s < 0:
            return 0
        if i == N:
            if s == 0:
                return 1
            return 0
        ret = (2 * f(s, i+1) % MOD + f(s-A[i], i+1)) % MOD
        cache[(s, i)] = ret
        return ret
    return f

def solve(N: int, S: int, A: "List[int]"):
    f = gen_f(N, A)
    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:
# -*- 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] for i in range(S+1)]
  for i in range(a+1,S+1):
    answer_next[i] += answer[i-a]
  if a<=S:
    answer_next[a] += power2
  power2 = (2*power2)%mod
  answer = [answer_next[i]%mod for i in range(S+1)]

print(answer[S])

Submission status: Time Limit Exceeded

Solution code:
N,S=map(int,input().split())
A=[int(i) for i in input().split()]
mod=998244353
dp=[[0 for j in range(S+1)]for i in range(N+1)]
pow2N=pow(2,N,mod)
dp[0][0]=pow2N
inv2=pow(2,mod-2,mod)
for i in range(N):
    for j in range(S+1):
        if dp[i][j]!=0:
            dp[i+1][j]+=dp[i][j]
            dp[i+1][j]%=mod
            if j+A[i]<=S:
                dp[i+1][j+A[i]]+=(inv2*dp[i][j])%mod
                dp[i+1][j+A[i]]%=mod
print(dp[N][S])

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from copy import copy

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

    # iである個数
    dp = [[0] * (s + 1) for _ in range(n)]
    dp[0][0] = 2
    if a[0] <= s:
        dp[0][a[0]] = 1

    for i, x in enumerate(a[1:], 1):
        dp[i] = [y * 2 for y in dp[i-1]]
        for j in range(s + 1):
            cur = j + x
            if cur > s:
                continue
            dp[i][cur] += dp[i - 1][j]

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


if __name__ == '__main__':
    main()

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
ans = 0
for a in A:
    newDP = defaultdict(int)
    for (sm, cnt), v in dp.items():
        # 追加しない
        newDP[(sm, cnt)] += v
        newDP[(sm, cnt)] %= mod
        # 追加する
        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:
#!/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
    for a in A:
        for (left, right) in sorted(d.keys(), reverse=True):
            if left + a > S:
                continue
            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:
Q = 998244353
def main():
    N, S = map( int, input().split())
    A = list( map( int, input().split()))
    invtwo = pow(2, Q-2, Q)
    # Invtwo = [1]
    # now = 1
    dp = [pow(2, N, Q)]+[0]*S
    for i in range(N):
        a = A[i]
        for i in range(S, a-1,-1):
            # print(i, a, i-a, dp[i-a])
            if dp[i-a] > 0:
                dp[i] += dp[i-a]*invtwo%Q
                dp[i] %= Q
        # print(dp)
    print(dp[S])
                
if __name__ == '__main__':
    main()

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
a.sort()
#print(a)
dp = [0] * (S + 1)
dp[0] = 1
for i in range(N):
  for x in range(S, -1, -1):
    if dp[x] == 0: continue
    if x + a[i] <= S:
      dp[x + a[i]] += dp[x] * pow(2, mod - 2, mod)
      dp[x + a[i]] %= mod
print(dp[-1] * pow(2, N, mod) % mod)

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
# dp[n][i][s] := i 番目まで見て n 個使って合計が s になる場合の数 これは無理
# dp[i][s] := i 番目まで見て合計 s 
dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
mod = 998244353
for i, a in enumerate(A, 1):
    for s in range(S+1):
        if s-a >= 0:
            dp[i][s] = (dp[i-1][s] * 2 + dp[i-1][s-a]) % mod
        else:
            dp[i][s] = dp[i-1][s] * 2 % mod
print(dp[N][S])

Submission status: Time Limit Exceeded

Solution code:
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]:
      for xj in x[j]:
        x[j+ai].append(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)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as fac

n, s = map(int, input().split())
l = [int(i)for i in input().split()]
l.sort(reverse=True)
mod = 998244353

z = 0


def f(i, tot, nn):
    global z
    if tot > s:
        return
    elif tot == s:
        z += 2 ** (n - nn)
        z %= mod
    else:
        for j in range(i, n):
            f(j + 1, tot + l[j], nn + 1)


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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as fac

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

z = 0


def f(i, tot, nn):
    # print(st)
    #print(i, tot, nn)
    global z
    if tot > s:
        return
    elif tot == s:
        z += 2 ** (n - nn)
        z %= mod
    else:
        for j in range(i, n):
            f(j + 1, tot + l[j], nn + 1)


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

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 998244353

def solve():
    n,s = LI()
    a = LI()
    dp = [[0]*(n+1) for i in range(s+1)]
    dp[0][0] = 1
    for i in range(n):
        ai = a[i]
        for j in range(i+1)[::-1]:
            nj = j+1
            for k in range(s)[::-1]:
                if dp[k][j] == 0:
                    continue
                nk = k+ai
                if nk > s:
                    continue
                dp[nk][nj] += dp[k][j]
    ans = 0
    for i in range(n+1):
        if dp[s][i]:
            ans += dp[s][i]*pow(2,n-i,mod)%mod
            ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

M =998244353

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

Submission status: Time Limit Exceeded

Solution code:
dp = [[0]*3001 for _ in range(3001)]
n,s = (int(num) for num in input().split())
a = [int(num) for num in input().split()]
MOD = 998244353
dp[0][0] = 1
for i in range(1,n+1):
    for j in range(s+1):
        dp[i][j] = (dp[i-1][j] * 2) % MOD
        if j >= a[i-1]:
            dp[i][j] = (dp[i][j] + dp[i-1][j-a[i-1]])%MOD
            
print(dp[n][s])

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
class mint:
    def __init__(self, i):
        self.i = i
    def __add__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __radd__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __mul__(self, m):
        return mint(self.i * (m.i if isinstance(m, mint) else m) % MOD)
    def __sub__(self, m):
        t = self.i - (m.i if isinstance(m, mint) else (m % MOD))
        if t < 0:
            t += MOD
        return mint(t)
    def __pow__(self, m):
        i = self.i
        return mint(pow(i, m, MOD))
    def __truediv__(self, m):
        return mint(self.i * pow(m, MOD - 2, MOD) % MOD)
    def __repr__(self):
        return repr(self.i)


n, s = map(int, input().split())
dp = [mint(0)] * (s + 1)
dp[0] = mint(2) ** n
i2 = mint(2) ** (MOD-2)
for a in map(int, input().split()):
    for i in range(s, -1, -1):
        if a + i <= s:
            dp[a + i] += dp[i] * i2
print(dp[s])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

n, s = nm()
a = nl()
mod = 998244353
dp = [0]*(s+1)
dp[0] = 1
for i in range(n):
    v = a[i]
    for j in range(s, -1, -1):
        dp[j] = (dp[j]*2 + dp[(j-v) % s]*(j >= v)) % mod
print(dp[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 = [{} for _ in range(S + 1)]
    dp[0][0] = 1
    for a in A:
        for i in reversed(range(a, S + 1)):
            for k, v in dp[i - a].items():
                dp[i][k + 1] = dp[i].get(k + 1, 0) + v
    r = 0
    for k, v in dp[S].items():
        r += pow(2, N - k, mod) * v
        r %= mod
    return r

print(main())

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

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

dp = [0] * (s+2)

dp[0] = 1

for a in As:
    for i in range(s+1, -1, -1):
        if i - a < 0:continue
        dp[i] += dp[i-a] * (MOD+1) // 2
        dp[i] %= MOD

print(dp[s] * pow(2, n, MOD) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

dp = defaultdict(int)
dp[(0,0)] = 1
for a in A:
    for (size,total),cnt in tuple(dp.items()):
        if total+a <= S:
            dp[(size+1,total+a)] += cnt
            dp[(size+1,total+a)] %= MOD

res = 0
c = 1
for size in reversed(range(1,N+1)):
    res += c*dp[(size,S)]
    res %= MOD
    c *= 2
    c %= 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

from collections import Counter
import copy

C=Counter()
C[(0,0)]=1

for a in A:
    C2=copy.deepcopy(C)
    for s,k in C:
        if s+a<=S:
            C2[(s+a,k+1)]+=C[(s,k)]
    C=C2
        
    
ANS=0
for s,k in C:
    if s==S:
        ANS=(ANS+pow(2,N-k,mod)*C[(s,k)])%mod
print(ANS)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

for i, a in enumerate(A, start=1):
    for n in range(i)[::-1]:
        for s in range(S + 1):
            if s + a <= S:
                dp[n + 1][s + a] = (dp[n + 1][s + a] + dp[n][s]) % MOD

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())


n,s=sep()
ar=lis()
ar.insert(0,0)
dp=[[0]*(s+2) for _ in range(n+2)]
dp[0][0]=1
N=998244353
for i in range(1,n+1):
    for j in range(0,s+1):
        dp[i][j]=(2*dp[i-1][j])%N
        if j-ar[i]>=0:
            dp[i][j]=(dp[i][j]+dp[i-1][j-ar[i]])%N
#print(dp)
print(dp[n][s])

Submission status: Accepted

Solution code:
import sys
import copy

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, S = in_nn()
    A = in_nl()

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

    mod = 998244353
    for i in range(N):
        next_dp = [0] * (S + 1)
        for j in range(S + 1):
            next_dp[j] += dp[j] * 2
            next_dp[j] %= mod
            if j + A[i] <= S:
                next_dp[j + A[i]] += dp[j]
                next_dp[j + A[i]] %= mod

        dp = next_dp

    print(dp[S])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,S=map(int,input().split())
*a,=map(int,input().split())
mod=998244353

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]=2*dp[i][j]

        if j>=a[i]:
            dp[i+1][j]+=dp[i][j-a[i]]
        
        dp[i+1][j]%=mod

print(dp[N][S])

Submission status: Accepted

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

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

"""
X = (1,2,...,N)の部分集合
Y = Xの部分集合

各i(1 ≤ i ≤ N) について、
1. XにもYにも入れる
2. Xには入れるがYには入れない
3. XにもYにも入れない

dp[i][j] = i番目までの選択をして、sum(Y)==jであるような場合の数
"""

dp = [[0 for _ in range(S + 1)]for _ in range(N + 1)]
dp[0][0] = 1
for i in range(1, N + 1):
    for j in range(S + 1):
        # YにA[i]を入れることが出来る場合（遷移元がある場合）
        # 選択肢2,3を選ぶ場合 + 選択肢1を選ぶ場合
        if j >= A[i]:
            dp[i][j] = 2 * dp[i - 1][j] + dp[i - 1][j - A[i]]
            dp[i][j] %= mod
        # 選択肢2,3を選ぶ場合(1は選べない)
        else:
            dp[i][j] = 2 * dp[i - 1][j]
            dp[i][j] %= mod

print(dp[N][S])

Submission status: Accepted

Solution code:
N, S = map(int, input().split())
MOD = 998244353
A = list(map(int, input().split()))
dp = [0]*(S+1)
dp[0] = 1
for a in A:
    for s in reversed(range(S+1)):
        if s+a<=S: dp[s+a] += dp[s]
        dp[s] *= 2
        dp[s] %= MOD
print(dp[S]%MOD)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit, i8


@njit(i8(i8, i8, i8[:]), cache=True)
def solve(N, S, A):
    MOD = 998244353
    dp = np.zeros((N + 1, S + 1), dtype=np.int64)
    dp[0][0] = 1
    for i in range(N):
        for j in range(S + 1):
            dp[i + 1][j] += 2 * dp[i][j]
            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
    return dp[-1][-1]


N, S = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)
print(solve(N, S, A))

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,S = MI()
A = [0] + LI()
mod = 998244353

dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
    for j in range(S+1):
        if j >= A[i]:
            dp[i][j] = 2*dp[i-1][j] + dp[i-1][j-A[i]]
            dp[i][j] %= mod
        else:
            dp[i][j] = 2*dp[i-1][j]
            dp[i][j] %= mod

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N,S = MI()
A = [0] + LI()
mod = 998244353

dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
    for j in range(S+1):
        if j >= A[i]:
            dp[i][j] = 2*dp[i-1][j] + dp[i-1][j-A[i]]
            dp[i][j] %= mod
        else:
            dp[i][j] = 2*dp[i-1][j]
            dp[i][j] %= mod

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

Submission status: Accepted

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

DIV = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))

# ある数の取り得る状態は以下
# (1)部分集合Pに含まれない
# (2)部分集合Pに含まれ、和に使われている
# (3)部分集合Pに含まれ、和に使われていない

# dp[i][j][k] = i - 1個目まで処理したときに、部分集合Pに含まれ(j)、総和がkになっている個数
dp = [[[0] * (S + 1) for j in range(2)] for i in range(N + 1)]
dp[0][0][0] = 1

for i in range(N):
  for k in range(S + 1):
    # (1)部分集合Pに含まれない
    dp[i + 1][0][k] += dp[i][0][k]
    dp[i + 1][0][k] += dp[i][1][k]
    dp[i + 1][0][k] %= DIV

    # (2)部分集合Pに含まれ、和に使われている
    if k + A[i] <= S:
      dp[i + 1][1][k + A[i]] += dp[i][0][k]
      dp[i + 1][1][k + A[i]] += dp[i][1][k]
      dp[i + 1][1][k + A[i]] %= DIV

    # (3)部分集合Pに含まれ、和に使われていない
    dp[i + 1][1][k] += dp[i][0][k]
    dp[i + 1][1][k] += dp[i][1][k]
    dp[i + 1][1][k] %= DIV

print((dp[-1][0][-1] + dp[-1][1][-1]) % DIV)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()


def main():
    n, s = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 998244353
    dp = np.zeros(3001, dtype=np.int64)
    dp[0] = 1
    for AA in A:
        dp = dp*2+np.concatenate([np.zeros(AA, dtype=np.int64), dp[:3001-AA]])
        dp %= mod
    print(dp[s])





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

MOD = 998244353

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

dp = np.zeros((N, S + 1))
dp[0, 0] = 2
if A[0] < S + 1:
	dp[0, A[0]] = 1

for i in range(1, N):
	dp[i, :] = (2 * dp[i - 1, :]) % MOD
	if A[i] > S:
		continue
	dp[i, A[i] : S + 1] += dp[i - 1, 0 : S - A[i] + 1]
	dp[i, :] %= MOD
print(int(dp[N - 1, S]))

Submission status: Accepted

Solution code:
MOD = 998244353

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

dp = [[0] * (S + 1) for i in range(N)]
dp[0][0] = 2
if A[0] < S + 1:
	dp[0][A[0]] = 1

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

Submission status: Accepted

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [0 for _ in range(S+1)]
visited = [0]
dp[0] = 1
dp = tuple(dp)
for k in range(N):
  a = A[k]
  nextdp = list(dp)
  nextvisit = []
  for item in visited:
    #process1
    if item + a <= S:
      if nextdp[item+a] == 0:
        nextvisit.append(item+a)
      nextdp[item+a] += dp[item]
      nextdp[item+a] %= mod
    #process2
    if item <= S:
      nextdp[item] += dp[item]
      nextdp[item] %= mod
  dp = tuple(nextdp)
  visited.extend(nextvisit)

print(dp[-1])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 998244353


def resolve():
    """ 愚直解 """
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        a = A[i - 1]
        for prev in range(i):
            for j in range(s + 1):
                dp[i][j] += dp[prev][j]
                if a + j > s:
                    continue
                dp[i][a + j] += dp[prev][j]
                dp[i][a + j] %= mod
    print(dp)
    res = 0
    for i in range(1, n + 1):
        res += dp[i][-1]
        res %= mod
    print(res)


def resolve2():
    """ DP + 累積和 """
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    cnt_num = [0] * (s + 1)
    cnt_num[0] = 1
    res = 0
    for i in range(1, n + 1):
        a = A[i - 1]
        for j in range(s + 1):
            dp[i][j] += cnt_num[j]
            dp[i][j] %= mod
            if a + j > s:
                continue
            dp[i][a + j] += cnt_num[j]
            dp[i][a + j] %= mod
        for k in range(s + 1):
            cnt_num[k] = cnt_num[k] + dp[i][k]
            cnt_num[k] %= mod
        res += dp[i][-1]
        res %= mod
    print(res)


if __name__ == '__main__':
    n, s = map(int, input().split())
    A = list(map(int, input().split()))
    resolve2()

Submission status: Accepted

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

mod = 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):
        dp[i+1][j] += 2*dp[i][j]
        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[N][S])