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

p = [[0 for k in range(N + 1)] for j in range(S + 1)]
p[0][0] = 1

for i in range(N):
    for j in range(S + 1):
        dp[i + 1][j] += dp[i][j] * 2
        p[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:
MOD = 998244353


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 998244353
 
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, S = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    dp=[0 for _ in range(S+1)]
    dp[0]=pow(2,N,mod)
    i2=pow(2,mod-2,mod)
    for i,a in enumerate(A):
        for s in range(S,a-1,-1):
                dp[s]+=(dp[s-a]*i2)%mod
                dp[s]%=mod
    print(dp[-1]%mod)






if __name__ == "__main__":
    main()

Submission status: Accepted

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 = [0 for i in range(S+1)]
dic[0] = 1

for a in A:
  for i in range(S+1)[::-1]:
    if i<=S:
      dic[i] *= 2
    if i>=a:
      dic[i] += dic[i-a]
print(dic[S]%998244353)

Submission status: Accepted

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

A.sort()

MOD = 998244353

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

Submission status: Accepted

Solution code:
import sys
from collections import OrderedDict
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 = {}
    dp[0] = 1
    for i, a in enumerate(A):
        # print(i, dp)
        ks = sorted(dp.keys())
        for k in ks[::-1]:
            # print(k)
            if k + a <= S:
                if k + a in dp:
                    dp[k + a] = (dp[k] + dp[k + a]) % MOD
                else:
                    dp[k + a] = dp[k]
            dp[k] = (dp[k] * 2) % MOD
    # print(dp)
    print(0 if S not in dp else dp[S])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline

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(n):
    ni = i + 1
    for j in range(s + 1):
        nj = j
        dp[ni][nj] += 2 * dp[i][j]
        dp[ni][nj] %= mod
        nj = j + A[i]
        if nj <= s:
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= mod
print(dp[n][s] % mod)

Submission status: Accepted

Solution code:
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(self.power_func(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(self.power_func(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __row__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

    def power_func(self,a,n,p):
        bi=str(format(n,"b"))#2進表現に
        res=1
        for i in range(len(bi)):
            res=(res*res) %p
            if bi[i]=="1":
                res=(res*a) %p
        return res

    def combination(self,n,r=-1):
        if r==-1:
            r = n
        #nCrの一覧を返す。rの上限も
        if (r<0) or (n<r):
            return 0
        cur = ModInt(1)
        res = []
        res.append(cur)
        for i in range(1,r+1):
            cur *= n + 1 -i
            cur /= i
            res.append(cur)
        return res

MOD = 998244353
#グローバル変数MODを決めてあげてください
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

N,S = [int(hoge) for hoge in input().split()]
A = [int(hoge) for hoge in input().split()]

DP = [[0]*(S+1) for i in range(N+1)]#DP[k][x] = i個みて和がx 
DP[0][0] = 1
Modi2 = mod_inv(2,MOD)
for i in range(N):
    a = A[i]
    #くばるDP
    for s,d in enumerate(DP[i]):
        DP[i+1][s] += DP[i][s]
        DP[i+1][s] %= MOD
        Diff = d*Modi2
        Diff %= MOD
        if s + a  <= S:
            DP[i+1][s+a] += Diff
            DP[i+1][s+a] %= MOD

two = ModInt(2)
twotwo = two ** ModInt(N)
print(DP[N][S] * twotwo)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

n,s=l_in()
A=l_in()


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

dp[0][0]=1


mod = 998244353

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

        dp[i][w] =         dp[i][w]%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] * 4000 for _ in range(4000)]

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

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

    return K * x % mod

inv2 = pow_k(2, mod - 2)
pow2n = pow_k(2, n)

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

Submission status: Accepted

Solution code:
import sys

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

def main():
    n, s = LI()
    a = LI()
    dp = [[0 for i in range(s+1)] for j in range(n+1)]
    dp[0][0] = 1

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

    print(dp[n][s])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def getN():
    return int(input())


def getNM():
    return map(int, input().split())


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


from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys

# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *


def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1 / f


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret


def bunsu(n):
    ret = []
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            tmp = 0
            while (True):
                if n % i == 0:
                    tmp += 1
                    n //= i
                else:
                    break
            ret.append((i, tmp))

    ret.append((n, 1))
    return ret

MOD = 998244353
def solve():
    n, k = getList()
    nums = getList()
    dp = [0 for i in range(k+1)]
    dp[0] = 1
    for i, num in enumerate(nums):
        new = [0 for i in range(k+1)]
        for j, d in enumerate(dp):
            new[j] += d * 2
            if (j + num) <= k:
                new[j+num] += d

        dp = [ne%MOD for ne in new]
    print(dp[-1])

def main():
    # n = getN()
    # for _ in range(n):
    solve()


if __name__ == "__main__":
    solve()

Submission status: Accepted

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(S+1, np.int64)
dp[0] = 1
for a in A:
    prev = dp.copy()
    dp[a:] += dp[:-a]
    dp += prev
    dp %= MOD

answer = dp[S]
print(answer%MOD)

Submission status: Accepted

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

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

    mod = 998244353

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 998244353

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

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

Submission status: Accepted

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

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

n,s = readints()
a = readints()

mod = 998244353

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

a.sort()

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

for i in range(1,n+1):
    x = a[i-1]
    for j in range(1,s+1):
        if 0<=j-x:
            dp[i][j] += (dp[i-1][j-x]*z + dp[i-1][j])%mod
        else:
            dp[i][j] += dp[i-1][j]


print(dp[n][s]%mod)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

note = [[0 for i in range(S+1)] for n in range(N+1)]

for n in range(1,N+1):
  for i in range(1,S+1):
    if A[n]>i:
      note[n][i] = (note[n-1][i]*2) % mod
    elif A[n] == i:
      note[n][i] = (note[n-1][i]*2 + pow(2,n-1,mod)) % mod
      note[n][i] = note[n][i] % mod 
    else:
      note[n][i] = (note[n-1][i] * 2 + note[n-1][i-A[n]]) % mod
      note[n][i] = note[n][i] % mod
  #print(note)
print(note[N][S] % mod)

Submission status: Accepted

Solution code:
import numpy as np

mod = 998244353

n, s = map(int, input().split())
A = list(map(int, input().split()))
DP = np.zeros(3005, dtype=np.int64)

for num, a in enumerate(A):
    double = DP * 2
    shift = np.hstack([np.zeros(a), DP[:-a]]).astype(np.int64)
    DP = double + shift
    DP[a] += pow(2, num, mod)
    DP %= mod

print(DP[s])

Submission status: Accepted

Solution code:
mod = 998244353

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

table = [0]*(s+1)
table[0] = 1
ans = 0
for ai in a:
    nxt = [0]*(s+1)
    if ai <= s:
        for j in range(ai, s+1):
            nxt[j] = table[j-ai]
    table = [(2*table[i] + nxt[i])%mod for i in range(s+1)]
ans += table[-1]
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
def examA():
    A, B = LI()
    ans = A*B
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    for a in A:
        if a==0:
            print(0)
            return
    ans = 1
    for a in A:
        ans *= a
        if ans>10**18:
            print(-1)
            return
    print(ans)
    return

def examC():
    A, B = LSI()
    ans =math.floor(int(A)*float(B))
    print(ans)
    return

def examD():
    def factorization(n):
        arr = defaultdict(int)
        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[i] = cnt
        if temp != 1:
            arr[temp] = 1
        if arr == []:
            arr[n] = 1
        return arr
    C = [0,1,3,6,10,15,21,28,36,45]
    N = I()
    F = factorization(N)
    ans = 0
    #print(F)
    for f in F.values():
        for i in range(10):
            if C[i]>f:
                ans += i-1
                break
    print(ans)
    return

def examE():
    N = I()
    A = [0]*N
    B = [0]*N
    for i in range(N):
        A[i],B[i] = LI()
    A.sort()
    B.sort()
    if N%2==0:
        L = (A[N//2-1] + A[N//2])/2
        R = (B[N//2-1] + B[N//2])/2
        ans = int((R-L)*2) +1
    else:
        L = A[N//2]
        R = B[N//2]
        ans = (R-L)+1

    print(ans)
    return

def examF():
    inv = pow(2,mod2-2,mod2)
    N, S = LI()
    A = LI()
    dp = [[0]*(S+1)for _ in range(N+1)]
    dp[0][0] = pow(2,N,mod2)
    for i in range(N):
        a = A[i]
        for s in range(S+1):
            dp[i+1][s] += dp[i][s]
            dp[i+1][s] %= mod2
            if (s+a<=S):
                dp[i+1][s+a] += dp[i][s]*inv%mod2
                dp[i + 1][s+a] %= mod2
   # print(dp)
    ans = dp[-1][-1]%mod2
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<60
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

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

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

mod = 998244353
l = 3050

M = [1]  # i!のmod
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  # x**y の mod を返す関数
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  # x の mod での逆元を返す関数
    return pow(x, mod-2, mod)

D = [0] * 3050

M2 = [1]
M2I = [0] * l

for i in range(l-1):
    M2.append((M2[-1] * 2) % mod)
for i in range(l):
    M2I[i] = inv(M2[i], mod)

i2 = inv(2,mod)

D[0] = M2[n]
for i in range(n):
    for j in range(l-1,-1,-1):
        if j - A[i] >= 0:
            D[j] = (D[j] + D[j-A[i]] * i2) % mod
    # print(D[:10])
    
print(D[s])

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 998244353
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,S=LI()
DP = [[0 for i in range(S+1)] for j in range(N+1)]
LIS=LI()
DP[0][0]=1
for i in range(N):
    v = LIS[i]
    for j in range(S+1):
        if j-v >= 0:
            DP[i+1][j] = (2*DP[i][j] + DP[i][j-v])%DVSR
        else:
            DP[i+1][j] = (2*DP[i][j])%DVSR

print(DP[N][S])

Submission status: Accepted

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

print(dp[N][S])

Submission status: Accepted

Solution code:
N,S = list(map(int,input().split()))
A = list(map(int,input().split()))
dp = [[0]*(N+1) for i in range(S+1)]
p = 998244353

twos = [1]*N
for i in range(1,N):
    twos[i] = (twos[i-1]*2)%p

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

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(2)] for i in range(n + 1)]
dp[0][0][0] = 1


# 最後に選ぶとき 1
# 最後に選ばないとき 0
for i in range(n):
    for j in range(s + 1):
        # 選ぶとき
        if j + a[i] <= s:
            dp[i + 1][1][j + a[i]] += dp[i][0][j] + dp[i][1][j]
            dp[i + 1][1][j + a[i]] %= MOD
        # 選ばないとき
        dp[i + 1][0][j] += (dp[i][0][j] + dp[i][1][j]) * 2
        dp[i + 1][0][j] %= MOD
ans = 0
for i in range(n + 1):
    ans += dp[i][1][-1] * pow(2, (n - i), MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque,defaultdict
import heapq
from itertools import combinations
import bisect


mod=998244353
pp=pow(2,mod-2,mod)

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

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

for i in range(n):
    for j in range(s+1):
        if dp[i][j]>=1:
            if j+l[i]<=s:
                dp[i+1][j+l[i]]+=dp[i][j]*pp# +pow(2,n-1,mod)
                dp[i+1][j+l[i]]%=mod
            dp[i+1][j]+=dp[i][j]
            dp[i+1][j]%=mod
print(dp[-1][-1]%mod)

Submission status: Accepted

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

mod = 998244353

def power(n,e):
    ret = 1
    b = n
    while e:
        if e % 2 != 0:
            ret *= b
        ret %= mod
        b *= b
        b %= mod
        e //= 2
    return ret

def div(n1,n2):
    return n1*power(n2,mod-2)%mod

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

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

Submission status: Accepted

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

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

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

for a in A:
    for j in range(S, -1, -1):
        if j-a >= 0:
            dp[j] = dp[j]*2 + dp[j-a]
        else:
            dp[j] = dp[j]*2

print(dp[S]%mod)

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

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

Submission status: Accepted

Solution code:
n,s = map(int,input().split())
a = list(map(int,input().split()))
if n == 1:
    if a[0] == s:
        print(1)
        quit()
    else:
        print(0)
        quit()

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

Submission status: Accepted

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

def solve(N, S, A):
    mod = 998244353
    dp = [0] * (S + 1)
    dp[0] = pow(2, N, mod)
    div2 = pow(2, mod - 2, mod)
    m = 0
    for a in A:
        m += a
        for i in reversed(range(a, min(S, m) + 1)):
            dp[i] = (dp[i] + dp[i - a] * div2) % mod
    return dp[S]

print(main())

Submission status: Accepted

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

def main():
    N,S = map(int,input().split())
    a = list(map(int,input().split()))
    MOD = 998244353

    dp = [0]*(S+1)
    dp[0] = 1
    for num in a:
        dp2 = dp.copy()
        for i in range(S-num+1):
            dp2[num+i] += dp[i]
        for i in range(S+1):
            dp[i] += dp2[i]
            dp[i] %= MOD
    
    print(dp[-1]%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

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


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

dp = np.zeros(s,"int64")

for i in range(n):
    
    newdp = dp.copy()
    if a[i]<s:
        newdp[a[i]:] += dp[:s-a[i]] * fac_inv2 % MOD
    if a[i]<=s:
        newdp[a[i]-1] += 1
    dp = newdp % MOD

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

Submission status: Accepted

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