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: Accepted

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

MOD = 998244353


def main(input, print):
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[0 for _ in range(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[n][s])


if __name__ == '__main__':
    main(sys.stdin.readline, print)

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):
    dp[i][j]+=dp[i-1][j]*2
    if j-A[i-1]>=0:
      dp[i][j]+=dp[i-1][j-A[i-1]]
    dp[i][j]%=mod
print(dp[N][S])

Submission status: Accepted

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+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])

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N,S=map(int, input().split())
    A = list(map(int,input().split()))
    mod = 998244353
    dp = [[0]*(S+1) for i in range(N+1)]
    dp[0][0]=1
    for i in range(N):
        vi = A[i]
        for j in range(S+1):
            dp[i+1][j] += 2 * dp[i][j]
            dp[i+1][j] %= mod
            if j+vi<=S:
                dp[i+1][j+vi] += dp[i][j]
                dp[i+1][j+vi] %= mod

    print(dp[N][S])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 998244353

dp = [[0]*(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] = (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[N][S])

Submission status: Accepted

Solution code:

import sys, io, os, re
import bisect
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce

def array1(n): return [0] * n
def array2(n, m): return [[0] * m for x in range(n)]
def array3(n, m, l): return [[[0] * l for y in xrange(m)] for x in xrange(n)]

n, s = list(map(int, sys.stdin.readline().strip().split()))
a = [0 for x in range(n)]
a = list(map(int, sys.stdin.readline().strip().split()))

mod = 998244353

d = array2(n+1, s+1)
d[0][0] = 1

for i in range(n):
    #print(d)
    for j in range(s+1):
        d[i+1][j] += d[i][j] * 2
        d[i+1][j] %= mod
        if j + a[i] <= s:
            d[i+1][j+a[i]] += d[i][j]
            d[i+1][j+a[i]] %= mod

#print(d)
print(d[n][s])

Submission status: Accepted

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

MOD = 998244353


dp = [[0 for i in range(s + 1)] for j in range(n + 1)]

dp[0][0] = 1

for i in range(n):
    for 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][-1])

Submission status: Accepted

Solution code:
N, S, *A = map(int, open(0).read().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] += 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][-1])

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

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

def resolve():
    ward = 96
    n, s = map(int, input().split())
    mask = int(('1' * 32 + '0' * 64) * (s + 1) , 2)
    Mask = (1 << (s + 1) * ward) - 1
    dp = 1
    for a in map(int, input().split()):
        dp = (dp * 2) + (dp << ward * a)
        dp &= Mask
        dp = (dp & (~mask)) + ((dp & mask) >> 64) * ((1 << 64) % MOD)

    print(((dp >> s * ward) & ((1 << ward) - 1)) % MOD)
resolve()

Submission status: Accepted

Solution code:
def main():
    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):
        ai = a[i-1]
        for j in range(min(s+1, ai)):
            dp[i][j] += dp[i-1][j]*2
            dp[i][j] %= mod
        for j in range(ai, s+1):
            dp[i][j] += dp[i-1][j]*2 + dp[i-1][j-ai]
            dp[i][j] %= mod
    print(dp[n][s])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
N,S=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

mod=998244353
cur=defaultdict(lambda: 0)
new=defaultdict(lambda: 0)
cur[0]=1

for a in A:
    for i in cur.keys():
        if i+a<=S:
            new[i+a]+=cur[i]
            new[i+a]%=mod
        new[i]+=cur[i]*2
        new[i]%=mod
    cur=new
    new=defaultdict(lambda: 0)

print cur[S]

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
N,S=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

mod=998244353
cur=defaultdict(lambda: 0)
new=defaultdict(lambda: 0)
cur[0]=1

for a in A:
    for i in cur.keys():
        if i+a<=S:
            new[i+a]+=cur[i]*1
            new[i+a]%=mod
        new[i]+=cur[i]*2
        new[i]%=mod
    cur=new
    new=defaultdict(lambda: 0)

print cur[S]

Submission status: Accepted

Solution code:
import numpy as np

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

mod = 998244353
dp = np.zeros(s+1, dtype='i8')
dp[0] = 1
for aa in a:
    tmp = 2 * dp % mod
    tmp[aa:] += dp[:-aa]
    tmp %= mod
    dp = tmp
print(dp[s])

Submission status: Accepted

Solution code:
n, s = map(int, input().split())
a = [int(i) for i in input().split()]

mod = 998244353
dp = [[0]*(s+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for k in range(s+1):
        dp[i+1][k] += 2 * dp[i][k]
        dp[i+1][k] %= mod
        if k+a[i] <= s:
            dp[i+1][k+a[i]] += dp[i][k]
            dp[i+1][k+a[i]] %= mod
print(dp[n][s])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 998244353
n, s = map(int, input().split())
A = map(int, input().split())
dp = [0]*(s+1)
dp[0] = 1
inv_2 = (MOD+1)//2
for a in A:
    for j in reversed(range(s+1)):
        if j-a < 0:
            continue
        dp[j] += dp[j-a]*inv_2
        dp[j] %= MOD

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
import numpy as np
N,S = map(int,input().split())
MOD = 998244353
A = list(map(int,input().split()))
dp = np.zeros(S+1,dtype = np.int64)
dp[0] = 2
if A[0] <= S:
    dp[A[0]] = 1
for i in range(1,N):
    a = A[i]
    p = dp*2
    if a <= S:
        p[a:] += dp[:-a]
    p %= MOD
    dp = p
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
import numpy as np
N,S = map(int,input().split())
MOD = 998244353
A = list(map(int,input().split()))
dp = np.zeros(S+1,dtype = np.int64)
dp[0] = 2
if A[0] <= S:
    dp[A[0]] = 1
for i in range(1,N):
    a = A[i]
    p = dp*2
    if a <= S:
        p[a:] += dp[:-a]
    p %= MOD
    dp = p
print(dp[S])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
import numpy as np
N,S = map(int,input().split())
MOD = 998244353
A = list(map(int,input().split()))
dp = np.zeros(3003,dtype = np.int64)
dp[0] = 2
if A[0] <= S:
    dp[A[0]] = 1
for i in range(1,N):
    a = A[i]
    p = dp*2
    p[a:] += dp[:-a]
    p %= MOD
    dp = p
print(dp[S])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]

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

Submission status: Accepted

Solution code:
from sys import stdin
def input():
    return stdin.readline()

def main():
    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(1,N+1) : 
        for j in range(S + 1) : 
            if(j==0):
                dp[i][j]+=pow(2,i,mod)
            else:
                dp[i][j]+=2*dp[i-1][j]
                dp[i][j]%=mod
                if(j-A[i-1]>=0):
                    dp[i][j]+=dp[i-1][j-A[i-1]]
            dp[i][j]%=mod
    print(dp[N][S]%mod)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import os
import sys
from io import BytesIO, IOBase
from sys import stdin
def input():
    return stdin.readline()

def main():
    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(1,N+1) : 
        for j in range(S + 1) : 
            if(j==0):
                dp[i][j]=pow(2,i,mod)
            else:
                dp[i][j]+=2*dp[i-1][j]
                dp[i][j]%=mod
                if(j-A[i-1]>=0):
                    dp[i][j]+=dp[i-1][j-A[i-1]]
            dp[i][j]%=mod
    print(dp[N][S]%mod)
    


# fast-io region

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


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input():
    return sys.stdin.readline().rstrip("\r\n")


def write(*args, end="\n"):
    for x in args[:-1]:
        sys.stdout.write(str(x) + " ")
    sys.stdout.write(str(args[-1]))
    sys.stdout.write(end)


def r_array():
    return [int(x) for x in input().split()]


def r_int():
    return int(input())


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
n,s,*a=map(int,open(0).read().split())
mod=998244353
d=np.zeros(s+1,dtype=np.int64)
d[0]=1
for x in a:
	p=d*2
	if x<=s:
		p[x:]+=d[:s-x+1]
	p%=mod
	d=p
print(d[-1])

Submission status: Accepted

Solution code:
import sys

MOD = 998244353

def main():
    N, S = map(int, input().split())
    X = [int(x) for x in sys.stdin.readline().split()]

    # dp = np.zeros((N+1)*(S+1), dtype=np.int).reshape((N+1),(S+1))
    dp = [[0 for _ in range(S+1)] for _ in range(N+1)]

    dp[0][0] = 1

    for i in range(N):
        xi = X[i]
        # xi を U に加えない場合
        for j in range(S+1):
            dp[i+1][j] += dp[i][j]*2  # T に加える／加えない
            dp[i+1][j] %= MOD
            # xi を U に加える場合
            if j+xi > S: continue
            dp[i+1][j+xi] += dp[i][j]
            dp[i+1][j+xi] %= MOD

    print(dp[N][S] % MOD)

main()

Submission status: Accepted

Solution code:

import sys
MOD = 998244353


def main():
    input = sys.stdin.buffer.readline
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[None] * (s + 1) for _ in range(n + 1)]
#     dp[i][j]:=集合{1..i}の空でない部分集合T全てについて,和がjとなる部分集合の個数の和
    for i in range(n + 1):
        for j in range(s + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
                continue
            if j > a[i - 1]:
                dp[i][j] = dp[i - 1][j] * 2 + dp[i - 1][j - a[i - 1]]
            elif j == a[i - 1]:
                dp[i][j] = dp[i - 1][j] * 2 + pow(2, i - 1, MOD)
            else:
                dp[i][j] = dp[i - 1][j] * 2
            dp[i][j] %= MOD
    print(dp[n][s])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N, S = map(int, input().split())
    A = list(map(int, input().split()))

    #output
    mod = 998244353
    dp = [[0] * ( S+1) for _ in range(N+1)]
    #dp[i, j]を、A[0]...A[i]までを使って、Tの空でない部分集合
    #{x_1, x_2, ..., x_k}であって、Ax_1 + A_x_2 + ... + A_x_k = jを満たすものの個数とする。
    dp[0][0] = 1
    #iまででjが作られている時、i+1ではA[i]がどのような値であっても、部分集合としてjは作れる。
    #iまででjが作られない時、j-A[i]が作られていれば、A[i]を足せばjは作れる。
    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]:
                dp[i+1][j] += dp[i][j-A[i]]
                dp[i+1][j] %= mod
                    
    print(dp[N][S] % mod)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,copy
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

mod = 998244353
n,s = inpl()
a = inpl()
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
        if j - a[i] >= 0:
            dp[i+1][j] += dp[i][j-a[i]]
        dp[i+1][j] %= mod
# print(dp)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 998244353

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, S = read_values()
    A = read_list()

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

    for i, a in enumerate(A):
        for s in range(S + 1):
            dp[i + 1][s] += 2 * dp[i][s]
            dp[i + 1][s] %= mod
            if s + a <= S: 
                dp[i + 1][s + a] += dp[i][s]
                dp[i + 1][s + a] %= mod
    
    print(dp[N][S])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 998244353
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N, S = read_ints()
A = read_ints()

# 惜しかったですね
# https://youtu.be/-fTsuyin-a8?t=9680

'''
dp[i][j]...[,i)の数の中の部分集合で、和をjにすることのできる通りの総数

更新則
dp[i + 1][j] = 2 * dp[i][j] + dp[i][j - A[i]]

∵
A[i]の使い方は3通り
1. 最初の部分集合に選ばれない
2. 部分集合の部分集合に選ばれない
3. Sを構成する和に選ばれる
1,2の遷移先は同じところから来るので×2がつく
'''

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

# print(*dp, sep='\n')
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 998244353
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N, S = read_ints()
A = read_ints()

# 包除？
# もしピッタリSを作ることのできる部分集合をかぶりなく複数構成できるとすると、その組み合わせを計算すればよい
# 求めたいものは→Sの部分和問題。なるべく細かく。背反に構成。
# 部分和復元してまた部分和？
# 3000*3000だから複数回DPはTLE

# 一回部分和を解いて、復元するときに分岐の数のを掛ければいいのでは？ #むしろ掛け算をDPするときにしちゃえばいいのでは？


# 1回部分和DPする
'''
dp[i][j]...[,i)の数の中の部分集合で、和をjにすることのできる通りの総数

使う可能性のあるものを全列挙できたらいいなぁ
'''

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

# print(*dp, sep='\n')
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)]
dp[0] = 1

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

print(dp[s])

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, a in enumerate(A):
    for j in range(S + 1):
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= MOD
        if j + a <= S:
            dp[i + 1][j + a] += dp[i][j]
            dp[i + 1][j + a] %= MOD

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect



class ModInt(int):

    MOD = None

    def __add__(self, other):
        self = ModInt(int.__add__(self, other) % ModInt.MOD)
        return self

    def __mul__(self, other):
        self = ModInt(int.__mul__(self, other) % ModInt.MOD)
        return self

def make_2d_arr(s1, s2, default=0):
    a = [None] * s1
    for i, _ in enumerate(a):
        a[i] = [default] * s2
    return a


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

    ModInt.MOD = 998244353
    dp = [ModInt(0)] * (s + 1)
    dp[0] = 1
    dp_arr = [dp, dp[:]]
    frm = 0
    to = 1

    for i in range(n):
        frm, to = to, frm
        for v in range(s + 1):
            dp_arr[to][v] = dp_arr[frm][v] * 2
            src = v - data[i]
            if src >= 0:
                dp_arr[to][v] += dp_arr[frm][src]
    #print('dp_arr') # debug
    #pp(dp_arr) # debug
    print(dp_arr[to][s])




    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Accepted

Solution code:
def f_knapsack_for_all_subsets_power_series(MOD=998244353, MAX=3010):
    # 参考: https://maspypy.com/atcoder-参加感想-2020-05-31abc-169
    import numpy as np
    N, S = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]

    f = np.zeros(MAX + 1, np.int64)  # 次数が S より大きな項には興味ないため、こうする
    f[0] = 1  # f_{0}(x) = 1
    for a in A:
        # f_{n+1} = f_{n} * (2 + x**a) = 2 * f_{n} + x**a * f_{n}
        f_next = 2 * f  # 第一項
        f_next[a:] += f[:-a]  # 第二項
        f_next %= MOD
        f = f_next
    return f[S]

print(f_knapsack_for_all_subsets_power_series())

Submission status: Accepted

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,3001),int)
# dp[j]:総和がjになるようにできる空でない部分集合の個数。
dp[0][0]=1 # 遷移用、実際は0

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

#print(dp)

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import sympy as syp(素因数分解とか)
Mod = 1000000007
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    n, s = map(int,input().split())
    a = list(map(int, input().split()))
    dp = [[0] * (s + 1) for i in range(n + 1)]
    #dp[i][j]...最初のi個の数について。総和がjであるように選んでできる部分集合すべてについての集合の個数の総和
    dp[0][0] = 1
    for i in range(n):
        for j in range(s+1):
            dp[i + 1][j] += dp[i][j] * 2 % 998244353
            if j - a[i] >= 0:
                dp[i + 1][j] += dp[i][j - a[i]]
            dp[i + 1][j] %= 998244353
            
    print(dp[n][s])
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
L = [0 for _ in range(S+1)]
L[0] = 1
F = {0}
for i in range(N):
  X = [[i, L[i]] for i in F]
  for j in F:
    L[j] *= 2
    L[j] %= mod
  for j in X:
    if A[i] + j[0] <= S:
      L[A[i]+j[0]] += j[1]
      L[A[i]+j[0]] %= mod
      F.add(A[i]+j[0])
print(L[S])

Submission status: Accepted

Solution code:
import numpy as np

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

MOD = 998244353

dp = np.zeros(s+1,dtype=int) #動的計画法を用いる
dp[0] = 1

for i in range(n):
    ddp = dp * 2 % MOD
    ddp[a[i]:] += dp[:-a[i]] #非常に大きな数になると考えられるため先にMOD計算を行う
    dp = ddp % MOD


print(dp[s])