Problem:


Score : 600 points

Problem Statement

Given are a sequence of N positive integers A_1, A_2, \ldots, A_N and another positive integer S.

For a non-empty subset T of the set \{1, 2, \ldots , N \}, let us define f(T) as follows:

f(T) is the number of different non-empty subsets \{x_1, x_2, \ldots , x_k \} of T such that A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.

Find the sum of f(T) over all 2^N-1 subsets T of \{1, 2, \ldots , N \}. Since the sum can be enormous, print it modulo 998244353.

Constraints

All values in input are integers.

1 \leq N \leq 3000

1 \leq S \leq 3000

1 \leq A_i \leq 3000

Input

Input is given from Standard Input in the following format:

N S
A_1 A_2 ... A_N

Output

Print the sum of f(T) modulo 998244353.

Sample Input 1

3 4
2 2 4

Sample Output 1

6

For each T, the value of f(T) is shown below. The sum of these values is 6.

f(\{1\}) = 0

f(\{2\}) = 0

f(\{3\}) = 1 (One subset \{3\} satisfies the condition.)

f(\{1, 2\}) = 1 (\{1, 2\})

f(\{2, 3\}) = 1 (\{3\})

f(\{1, 3\}) = 1 (\{3\})

f(\{1, 2, 3\}) = 2 (\{1, 2\}, \{3\})

Sample Input 2

5 8
9 9 9 9 9

Sample Output 2

0

Sample Input 3

10 10
3 1 4 1 5 9 2 6 5 3

Sample Output 3

3296



Sample input:
3 4
2 2 4


Sample output:
6

Submission status: Time Limit Exceeded

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


def main():
    n, s = map(int, input().split())
    a = np.array([int(i) for i in input().split()], dtype="int16")
    MOD = 998244353

    dp = np.zeros(s + 1, dtype="int64")
    dp[0] = 1

    for i in a:
        p = np.zeros(s + 1, dtype="int64")
        dp, p = p, dp
        dp += p * 2
        dp %= MOD
        for j in range(s + 1):
            # print(f"{i = }, {j = }, {dp = }, {p = }")
            if (ji := j + i) <= s:
                dp[ji] = (dp[ji] + p[j]) % MOD

    print(dp[s])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def main():
    n, s = map(int, input().split())
    a = [int(i) for i in input().split()]
    MOD = 998244353

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

    for i in a:
        p = [0] * (s + 1)
        dp, p = p, dp
        for j in range(s + 1):
            dp[j] += (p[j] * 2) % MOD
            dp[j] %= MOD
            if (ji := j + i) <= s:
                dp[ji] = (dp[ji] + p[j]) % MOD

    print(dp[s])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def main():
    n, s = map(int, input().split())
    a = [int(i) for i in input().split()]
    MOD = 998244353

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

    for i in a:
        p = [0] * (s + 1)
        dp, p = p, dp
        for j in range(s + 1):
            dp[j] += (p[j] * 2) % MOD
            dp[j] %= MOD
            if j + i <= s:
                dp[j + i] += p[j]
                dp[j + i] %= MOD

    print(dp[s])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

l=[]
for i in range(2):
    b = input().split()
    b = [ int(b[j]) for j in range(len(b))]
    l.append(b)

N = l[0][0]
X = l[0][1]
li =l[1]
li.sort()
s,count = 0,0
import itertools
import math
for i, _ in enumerate(li, 1):
    for j in itertools.combinations(li, r=i):  
        s = sum(j)
        p = X-s
        if s == X:
            count+=2**(N-i)
            if p < 0:
                break
    if sum(li[:i]) > X:
        break
print(count % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import itertools

a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
youso = [i for i in range(a[0])]
last=0
for j in range(1,a[0]+1):
    for i in itertools.combinations(youso,j):
        
        list = [b[n] for n in i]
        
        for n in range(1,len(list)+1):
            for n_1 in itertools.combinations(list,n):
                handan=0
                for n_2 in n_1:
                    handan+=n_2
                if handan == a[1]:
                    last+=1
print(last)

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

print(dp[n][s])

Submission status: Time Limit Exceeded

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


def main():
    N, S = map(int, input().split())
    *A, = map(int, input().split())
    dp = [[0]*(3001) for _ in range(N+1)]
    MOD = 998244353
    
    m = pow(2, MOD-2, MOD)
    dp[0][0] = pow(2, N, MOD)

    for i in range(1, N+1):    
        for j in range(3001):
            dp[i][j] += dp[i-1][j]
            if j-A[i-1]>=0:
                dp[i][j] += dp[i-1][j-A[i-1]]*m
            dp[i][j] %= MOD

    print(dp[N][S])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input=sys.stdin.readline


def main():
    N, S = map(int, input().split())
    *A, = map(int, input().split())
    dp = [[0]*(3001) for _ in range(N+1)]
    MOD = 998244353

    dp[0][0] = pow(2, N, MOD)
    for i in range(1, N+1):    
        for j in range(3001):
            dp[i][j] += dp[i-1][j]
            if j-A[i-1]>=0:
                dp[i][j] += dp[i-1][j-A[i-1]]*pow(2, MOD-2, MOD)

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


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input=sys.stdin.readline


def main():
    N, S = map(int, input().split())
    *A, = map(int, input().split())
    dp = [[0]*(3001) for _ in range(N+1)]
    MOD = 998244353
    ans = 0

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

    print(dp[N][S])


main()

Submission status: Time Limit Exceeded

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


def main():
    N, S = map(int, input().split())
    *A, = map(int, input().split())
    dp = [[0]*(3001) for _ in range(N+1)]
    MOD = 998244353
    ans = 0

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

    print(dp[N][S])


main()

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
*A, = map(int, input().split())
dp = [[0]*(3001) for _ in range(N+1)]
MOD = 998244353
ans = 0

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

print(dp[N][S])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

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

    print(DP[N][S])
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    N,S=pin()
    A=tupin()#調子にのるな
    mod=998244353
    
    #形式的冪級数を考える
    #普通の部分和ッ->集合内の各アイテムについて、選ぶか選ばないか。O(2^n)の探索
    #これを形式的冪級数でいえば、（1+x^a）を掛ける計算になる　指数時間ではない
    #つまり、集合A,Sに対して、[x^s]PI(1+x^a_i) (f_i)

    #次に、Aの部分集合について考える
    #サンプル1の場合、N==3なので8個の部分集合がある
    #つまり、F3＝1+(f_1+f_2+f_3)+(f1_f2+f2_f3+f3_f1)+f1_f2_f3を考える
    #果たして、一般的なNにたいして多項式時間でにFnをもとめれば指数時間は完全回避できる
    #F3=(1+f1+f2+f1f2)+f3{(1+f1+f2+f1f2)}
    #  =(1+f3)(1+f1+f2+f1f2)
    #  =(f3で追加された新しいところ)(N=2のときのすべての部分集合)

    #これは、f3をSの部分集合にふくめるか、含めないかの探索と同等
    #一般的にFn=F_n-1*(1+fn)=PI(1+fn)とわかる

    #求めるものは[x^S]PI(1+fn)=[x^S]PI(2+x^a)

    from collections import defaultdict #本当は良くないがわかりやすさのためココに置く
    from copy import deepcopy
    
    ans=defaultdict(int)#i
    ans[0]=1 #init ,1=x^0より
    #print(ans)
    for a in A:
        #ans そのものと、ansの係数にx^aをかけたものを足し算    
        temp=defaultdict(int)
        for x in ans:
            temp[x+a]=ans[x]
            
            ans[x]*=2
            ans[x]%=mod
        for t in temp:
            ans[t]+=temp[t]
            ans[t]%=mod
    print(ans[S])    
        
    
    
#%%submit!
resolve()

Submission status: Time Limit Exceeded

Solution code:
M=998244353
n,s,*l=map(int,open(0).read().split())
dp=[[0]*(s+1) for _ in '01']
dp[0][0]=1
b=0
for i in range(n):
  b^=1
  for j in range(s+1):
    dp[b][j]=dp[b^1][j]*2%M
    if j>=l[i]: dp[b][j]+=dp[b^1][j-l[i]]
print(dp[n%2][s]%M)

Submission status: Time Limit Exceeded

Solution code:
M=998244353
n,s,*l=map(int,open(0).read().split())
dp=[[0]*(s+1) for _ in '01']
dp[0][0]=1
b=0
for i in range(n):
  b^=1
  for j in range(s+1):
    dp[b][j]=dp[b^1][j]*2
    if j>=l[i]: dp[b][j]+=dp[b^1][j-l[i]]
    dp[b][j]%=M
print(dp[n%2][s])

Submission status: Time Limit Exceeded

Solution code:
import glob
import numpy as np

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\169\\F'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def resolve(self):

        tmp = self.input_data().split()
        N = int(tmp[0])
        S = int(tmp[1])
        tmp = self.input_data().split()
        A = [int(i) for i in tmp]
        A = np.array(A)
        A_sorted_index = np.argsort(A)

        # 集合全体に対してS=1-3000全ての組み合わせを格納するリスト
        combo_u_set = [[0]*(S+1) for i in range(S+1)]

        S_max = 0
        list_max = [1]*(S+1)
        # 集合全体に対してS(1-3000)ができる組み合わせを網羅
        for i in A_sorted_index:
            a = A[i]
            for j in range(S_max, 0, -1):
                # 今確認している位置の数とaの合計が3000を超えればスルー
                if j + a > S:
                    continue

                for k in range(1, list_max[j]):
                    if combo_u_set[j][k] == 0:
                        continue
                    combo_u_set[j+a][k+1] += combo_u_set[j][k]
                    if list_max[j+a] <= k+1:
                        list_max[j + a] = k + 2
            S_max += a
            if a <= S:
                combo_u_set[a][1] += 1
                if list_max[a] == 1:
                    list_max[a] = 2


        sum = 0
        # Sができる組み合わせが、何パターン作れるか合計
        for i in range(1, len(combo_u_set[S])):
            sum += (2 ** (N -i)) * combo_u_set[S][i]

        print(str(int(sum % 998244353)))


solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Time Limit Exceeded

Solution code:

import glob
import numpy as np

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\169\\F'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def resolve(self):

        tmp = self.input_data().split()
        N = int(tmp[0])
        S = int(tmp[1])
        tmp = self.input_data().split()
        A = [int(i) for i in tmp]
        A = np.array(A)
        A_sorted_index = np.argsort(A)

        # 集合全体に対してS=1-3000全ての組み合わせを格納するリスト
        combo_u_set = [[0]*(S+1) for i in range(S+1)]

        max = 0
        # 集合全体に対してS(1-3000)ができる組み合わせを網羅
        for i in A_sorted_index:
            a = A[i]
            for j in range(max, 0, -1):
                # 今確認している位置の数とaの合計が3000を超えればスルー
                if j + a > S:
                    continue

                for k in range(1, S):
                    combo_u_set[j+a][k+1] += combo_u_set[j][k]
            max += a
            if a <= S:
                combo_u_set[a][1] += 1


        sum = 0
        # Sができる組み合わせが、何パターン作れるか合計
        for i in range(1, len(combo_u_set[S])):
            sum += (2 ** (N -i)) * combo_u_set[S][i]

        print(str(int(sum % 998244353)))


solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Time Limit Exceeded

Solution code:
import glob
import numpy as np
import copy

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\169\\F'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def resolve(self):

        tmp = self.input_data().split()
        N = int(tmp[0])
        S = int(tmp[1])
        tmp = self.input_data().split()
        A = [int(i) for i in tmp]
        A = np.array(A)
        A_sorted_index = np.argsort(A)

        # 集合全体に対してS=1-3000全ての組み合わせを格納するリスト
        combo_u_set = [[] for i in range(S+1)]
        combo_u_set[0].append(0)

        max = 0
        # 集合全体に対してS(1-3000)ができる組み合わせを網羅
        for i in A_sorted_index:
            a = A[i]
            for j in range(max, -1, -1):
                # 今確認している位置の数とaの合計が3000を超えればスルー
                if j + a > S:
                    continue
                # jの位置の組み合わせにiを足したものをj+aの位置に追加
                if j == 0:
                    pass
                l = copy.copy(combo_u_set[j])
                for k in range(len(l)):
                    l[k] += 1
                combo_u_set[j+a].extend(l)
            max += a

        sum = 0
        # Sができる組み合わせが、何パターン作れるか合計
        for c in combo_u_set[S]:
            sum += 2 ** (N -c)

        print(str(sum % 998244353))


solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Time Limit Exceeded

Solution code:
import glob
import numpy as np
import copy

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\169\\F'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def resolve(self):

        tmp = self.input_data().split()
        N = int(tmp[0])
        S = int(tmp[1])
        tmp = self.input_data().split()
        A = [int(i) for i in tmp]
        A = np.array(A)
        A_sorted_index = np.argsort(A)

        # 集合全体に対してS=1-3000全ての組み合わせを格納するリスト
        combo_u_set = [[] for i in range(S+1)]
        combo_u_set[0].append(0)

        # 集合全体に対してS(1-3000)ができる組み合わせを網羅
        for i in A_sorted_index:
            a = A[i]
            for j in range(S, -1, -1):
                # 今確認している位置の数とaの合計が3000を超えればスルー
                if j + a > S:
                    continue
                # jの位置の組み合わせにiを足したものをj+aの位置に追加
                if j == 0:
                    pass
                l = copy.copy(combo_u_set[j])
                for k in range(len(l)):
                    l[k] += 1
                combo_u_set[j+a].extend(l)

        sum = 0
        # Sができる組み合わせが、何パターン作れるか合計
        for c in combo_u_set[S]:
            sum += 2 ** (N -c)
            sum = sum % 998244353

        print(str(sum))


solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Time Limit Exceeded

Solution code:
import glob
import numpy as np
import copy

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\169\\F'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def resolve(self):

        tmp = self.input_data().split()
        N = int(tmp[0])
        S = int(tmp[1])
        tmp = self.input_data().split()
        A = [int(i) for i in tmp]
        A = np.array(A)
        A_sorted_index = np.argsort(A)

        # 集合全体に対してS=1-3000全ての組み合わせを格納するリスト
        combo_u_set = [[] for i in range(S+1)]
        combo_u_set[0].append(0)

        # 集合全体に対してS(1-3000)ができる組み合わせを網羅
        for i in A_sorted_index:
            a = A[i]
            for j in range(S, -1, -1):
                # 今確認している位置の数とaの合計が3000を超えればスルー
                if j + a > S:
                    continue
                # jの位置の組み合わせにiを足したものをj+aの位置に追加
                if j == 0:
                    pass
                for s in combo_u_set[j]:
                    combo_u_set[j+a].append(s+1)

        sum = 0
        # Sができる組み合わせが、何パターン作れるか合計
        for c in combo_u_set[S]:
            sum += 2 ** (N -c)
            sum = sum % 998244353

        print(str(sum))


solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Time Limit Exceeded

Solution code:

import glob
import numpy as np
import copy

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\169\\F'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def resolve(self):

        tmp = self.input_data().split()
        N = int(tmp[0])
        S = int(tmp[1])
        tmp = self.input_data().split()
        A = [int(i) for i in tmp]
        A = np.array(A)
        A_sorted_index = np.argsort(A)

        # 集合全体に対してS=1-3000全ての組み合わせを格納するリスト
        combo_u_set = [[] for i in range(3001)]
        combo_u_set[0].append(0)

        # 集合全体に対してS(1-3000)ができる組み合わせを網羅
        for i in A_sorted_index:
            a = A[i]
            for j in range(3000, -1, -1):
                # 今確認している位置の数とaの合計が3000を超えればスルー
                if j + a > 3000:
                    continue
                # jの位置の組み合わせにiを足したものをj+aの位置に追加
                if j == 0:
                    pass
                for s in combo_u_set[j]:
                    combo_u_set[j+a].append(s+1)

        sum = 0
        # Sができる組み合わせが、何パターン作れるか合計
        for c in combo_u_set[S]:
            sum += 2 ** (N -c)
            sum = sum % 998244353

        print(str(sum))


solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Time Limit Exceeded

Solution code:

import glob
import numpy as np
import copy

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\169\\F'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def resolve(self):

        tmp = self.input_data().split()
        N = int(tmp[0])
        S = int(tmp[1])
        tmp = self.input_data().split()
        A = [int(i) for i in tmp]
        A = np.array(A)
        A_sorted_index = np.argsort(A)

        # 集合全体に対してS=1-3000全ての組み合わせを格納するリスト
        combo_u_set = [[] for i in range(3001)]
        combo_u_set[0].append([])

        # 集合全体に対してS(1-3000)ができる組み合わせを網羅
        for i in A_sorted_index:
            a = A[i]
            for j in range(3000, -1, -1):
                # 今確認している位置の数とaの合計が3000を超えればスルー
                if j + a > 3000:
                    continue
                # jの位置の組み合わせにiを足したものをj+aの位置に追加
                if j == 0:
                    pass
                for s in combo_u_set[j]:
                    l = copy.copy(s)
                    l.append(i)
                    combo_u_set[j+a].append(l)

        sum = 0
        # Sができる組み合わせが、何パターン作れるか合計
        for c in combo_u_set[S]:
            num = len(c)
            sum += 2 ** (N -num)
            sum = sum % 998244353

        print(str(sum))


solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

for i in range(1,N+1):
  for j in range(N+1):
    for k in range(S+1):
      dp[i][j][k]=dp[i-1][j][k]
      if k-alist[i-1]>=0:
        dp[i][j][k]+=dp[i-1][j-1][k-alist[i-1]]
      dp[i][j][k]%=MOD
#print(dp[-1])

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

Submission status: Time Limit Exceeded

Solution code:
N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
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: Time Limit Exceeded

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: Time Limit Exceeded

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

    print(dp[N][S])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

MOD = 998244353

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

Submission status: Time Limit Exceeded

Solution code:
#created by  nit1n
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] = 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: Time Limit Exceeded

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

MOD = 998244353

def solution(A, S):
    N = len(A)
    
    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 j >= A[i-1]:
                dp[i][j] += dp[i-1][j-A[i-1]]
                dp[i][j] %= MOD
    return dp[N][S]

print(solution(A, S))

Submission status: Time Limit Exceeded

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

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] += 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: Time Limit Exceeded

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

mod=998244353

N,S=nm()
A=nl()


dp=[[0]*3001  for _ in range(3001)]#i i番目 j和がj
dp[0][A[0]]=1
dp[0][0]=2
for i in range(1,N):
    for j in range(0,3001):
        if(0<=(j-A[i])):
            dp[i][j]=dp[i-1][j-A[i]]+2*dp[i-1][j]
        else:
            dp[i][j]=2*dp[i-1][j]
        dp[i][j]%=mod

ans=dp[N-1][S]
print(ans%mod)