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:
(n, s), *a = [[*map(int, t.split())] for t in open(0)]
a = a[0]
mem = [0] * (s + 1)
mem[0] = 1
mod = 998244353

for x in a:
    tmp = [2 * e for e in mem]
    if x <= s:
        for i in range(s - x + 1):
            tmp[i + x] += mem[i]
    mem = [e % mod for e in tmp]
print(mem[s])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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[N][S])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
nums = input().split()
num, goal = int(nums[0]), int(nums[1])
elements = input().split()
elements = [int(element) for element in elements]
ans = 0
for i in range(3**num):
    converted = ""
    for j in range(num-1, -1,-1):
        res = int(i / 3**j)
        i -= 3**j*res
        converted += str(res)
    selected = 0
    for k in range(num):
        if converted[k] == "2":
            selected += elements[k]
            if selected > goal:
                break
    if selected == goal:
        ans += 1
        if ans == 998244353:
            ans = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
nums = input().split()
num, goal = int(nums[0]), int(nums[1])
elements = input().split()
elements = [int(element) for element in elements]
ans = 0
for i in range(3**num):
    converted = ""
    for j in range(num-1, -1,-1):
        res = int(i / 3**j)
        i -= 3**j*res
        converted += str(res)
    selected = 0
    for k in range(num):
        if converted[k] == "2":
            selected += elements[k]
    if selected == goal:
        ans += 1
    if ans == 998244353:
        ans = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:

MOD = 998244353

class mint:
    def __init__(self, x):
        if isinstance(x, int):
            self.x = (x % MOD) if x >= MOD else x
        elif isinstance(x, mint):
            self.x = x.x
        else:
            x=int(x)
            self.x = (x % MOD) if x >= MOD else x
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        res = self.x + other.x if isinstance(other, mint) else other
        res -= MOD if res >= MOD else 0
        return mint(res)
    def __isub__(self, other):
        res = self.x + MOD-other.x if isinstance(other, mint) else MOD-other
        res -= MOD if res >= MOD else 0
        return mint(res)
    def __imul__(self, other):
        res = self.x * other.x if isinstance(other, mint) else other
        res %= MOD
        return mint(res)
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __floordiv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rfloordiv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

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

Submission status: Time Limit Exceeded

Solution code:

MOD = 998244353

class mint:
    def __init__(self, x):
        if isinstance(x, int):
            if x >= MOD:
                self.x = x % MOD
            else:
                self.x = x
        elif isinstance(x, mint):
            self.x = x.x
        else:
            x=int(x)
            self.x = (x % MOD) if x >= MOD else x
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    '''
    def __iadd__(self, other):
        res = self.x + other.x if isinstance(other, mint) else other
        res -= MOD if res >= MOD else 0
        return mint(res)
    def __isub__(self, other):
        res = self.x + MOD-other.x if isinstance(other, mint) else MOD-other
        res -= MOD if res >= MOD else 0
        return mint(res)
    def __imul__(self, other):
        res = self.x * other.x if isinstance(other, mint) else other
        res %= MOD
        return mint(res)
    '''
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __floordiv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rfloordiv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

n,s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[mint(0) for _ in range(s+1)] for _ in range(n+1)]
dp[0][0]=mint(pow(2,n,MOD))
div=mint(pow(2,MOD-2,MOD))
for i in range(n):
    for j in range(s+1):
        dp[i+1][j]=mint(dp[i][j])
        if j-a[i]>=0:
            dp[i+1][j]+=dp[i][j-a[i]]*div
print(dp[n][s])

Submission status: Time Limit Exceeded

Solution code:

MOD = 998244353

class mint:
    def __init__(self, x):
        if isinstance(x, int):
            if x >= MOD:
                self.x = x % MOD
            else:
                self.x = x
        elif isinstance(x, mint):
            self.x = x.x
        else:
            x=int(x)
            self.x = (x % MOD) if x >= MOD else x
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    '''
    def __iadd__(self, other):
        res = self.x + other.x if isinstance(other, mint) else other
        res -= MOD if res >= MOD else 0
        return mint(res)
    def __isub__(self, other):
        res = self.x + MOD-other.x if isinstance(other, mint) else MOD-other
        res -= MOD if res >= MOD else 0
        return mint(res)
    def __imul__(self, other):
        res = self.x * other.x if isinstance(other, mint) else other
        res %= MOD
        return mint(res)
    '''
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __floordiv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rfloordiv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

n,s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[mint(0) for _ in range(s+1)] for _ in range(n+1)]
dp[0][0]=mint(pow(2,n,MOD))
div=pow(2,MOD-2,MOD)
for i in range(n):
    for j in range(s+1):
        dp[i+1][j]=mint(dp[i][j])
        if j-a[i]>=0:
            dp[i+1][j]+=dp[i][j-a[i]]*div
print(dp[n][s])

Submission status: Time Limit Exceeded

Solution code:

MOD = 998244353

class mint:
    def __init__(self, x):
        if isinstance(x, int):
            if x >= MOD:
                self.x = x % MOD
            else:
                self.x = x
        elif isinstance(x, mint):
            self.x = x.x
        else:
            x=int(x)
            self.x = (x % MOD) if x >= MOD else x
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    '''
    def __iadd__(self, other):
        res = self.x + other.x if isinstance(other, mint) else other
        res -= MOD if res >= MOD else 0
        return mint(res)
    def __isub__(self, other):
        res = self.x + MOD-other.x if isinstance(other, mint) else MOD-other
        res -= MOD if res >= MOD else 0
        return mint(res)
    def __imul__(self, other):
        res = self.x * other.x if isinstance(other, mint) else other
        res %= MOD
        return mint(res)
    '''
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __floordiv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rfloordiv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

n,s = map(int, input().split())
a = list(map(int, input().split()))
import copy
dp = [[mint(0) for _ in range(s+1)] for _ in range(n+1)]
dp[0][0]=mint(pow(2,n,MOD))
div=pow(2,MOD-2,MOD)
for i in range(n):
    for j in range(s+1):
        dp[i+1][j]=copy.copy(dp[i][j])
        if j-a[i]>=0:
            dp[i+1][j]+=dp[i][j-a[i]]*div
print(dp[n][s])

Submission status: Time Limit Exceeded

Solution code:

MOD = 998244353

class mint:
    def __init__(self, x):
        if isinstance(x, int):
            if x >= MOD:
                self.x = x % MOD
            else:
                self.x = x
        elif isinstance(x, mint):
            self.x = x.x
        else:
            x=int(x)
            self.x = (x % MOD) if x >= MOD else x
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        res = self.x + other.x if isinstance(other, mint) else other
        res -= MOD if res >= MOD else 0
        return mint(res)
    def __isub__(self, other):
        res = self.x + MOD-other.x if isinstance(other, mint) else MOD-other
        res -= MOD if res >= MOD else 0
        return mint(res)
    def __imul__(self, other):
        res = self.x * other.x if isinstance(other, mint) else other
        res %= MOD
        return mint(res)
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __floordiv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rfloordiv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

n,s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[mint(0) for _ in range(s+1)] for _ in range(n+1)]
dp[0][0]=mint(pow(2,n,MOD))
div=pow(2,MOD-2,MOD)
for i in range(n):
    for j in range(s+1):
        dp[i+1][j]=dp[i][j]
        if j-a[i]>=0:
            dp[i+1][j]+=dp[i][j-a[i]]*div
print(dp[n][s])

Submission status: Time Limit Exceeded

Solution code:

MOD = 998244353

class mint:
    def __init__(self, x):
        if isinstance(x, int):
            self.x = (x % MOD) if x >= MOD else x
        elif isinstance(x, mint):
            self.x = x.x
        else:
            x=int(x)
            self.x = x % MOD if x >= MOD else x
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        res = self.x + other.x if isinstance(other, mint) else other
        res -= MOD if res >= MOD else 0
        return mint(res)
    def __isub__(self, other):
        res = self.x + MOD-other.x if isinstance(other, mint) else MOD-other
        res -= MOD if res >= MOD else 0
        return mint(res)
    def __imul__(self, other):
        res = self.x * other.x if isinstance(other, mint) else other
        res %= MOD
        return mint(res)
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __floordiv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rfloordiv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

n,s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[mint(0) for _ in range(s+1)] for _ in range(n+1)]
dp[0][0]=mint(pow(2,n,MOD))
div=pow(2,MOD-2,MOD)
for i in range(n):
    for j in range(s+1):
        dp[i+1][j]=dp[i][j]
        if j-a[i]>=0:
            dp[i+1][j]+=dp[i][j-a[i]]*div
print(dp[n][s])

Submission status: Time Limit Exceeded

Solution code:

MOD = 998244353

class mint:
    def __init__(self, x):
        if isinstance(x, int):
            self.x = x % MOD 
        elif isinstance(x, mint):
            self.x = x.x
        else:
            self.x = int(x) % MOD 
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        res = self.x + other.x if isinstance(other, mint) else other
        res -= MOD if res >= MOD else 0
        return mint(res)
    def __isub__(self, other):
        res = self.x + MOD-other.x if isinstance(other, mint) else MOD-other
        res -= MOD if res >= MOD else 0
        return mint(res)
    def __imul__(self, other):
        res = self.x * other.x if isinstance(other, mint) else other
        res %= MOD
        return mint(res)
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __floordiv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rfloordiv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

n,s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[mint(0) for _ in range(s+1)] for _ in range(n+1)]
dp[0][0]=mint(pow(2,n,MOD))
div=pow(2,MOD-2,MOD)
for i in range(n):
    for j in range(s+1):
        dp[i+1][j]=dp[i][j]
        if j-a[i]>=0:
            dp[i+1][j]+=dp[i][j-a[i]]*div
print(dp[n][s])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, s = map(int, input().split())
aa = tuple(sorted(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] += 2 * dp[i][j]
        dp[i + 1][j] %= MOD

        # j + a[i]を選んだ場合
        if j + aa[i] <= s:
            dp[i + 1][j + aa[i]] += dp[i][j]
            dp[i + 1][j + aa[i]] %= MOD
print(dp[n][s])

Submission status: Time Limit Exceeded

Solution code:
def sub_group(A):
    ret = []
    for i in range(1 << len(A)):
        output = []
        for j in range(len(A)):
            if ((i >> j) & 1) == 1:
                output.append(A[j])
        if output != []:
            ret.append(output)
    return ret

def f(X, validGroup):
    ret = 0
    pattern = sub_group(X)
    for candidate in pattern:
        if candidate in validGroup:
            ret += 1
    return ret

def main():
    MOD = 998244353
    n, s = map(int, input().split())
    a = [i for i in map(int, input().split())]
    
    validGroup = []
    sub_g = sub_group(a)
    for g in sub_g:
        if sum(g) == s:
            validGroup.append(g)

    ans = 0
    for g in sub_g:
        ans += f(g, validGroup)
    
    print(ans % MOD)


main()

Submission status: Time Limit Exceeded

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

Solution code:
from itertools import combinations

N, S = [int(i) for i in input().split(' ')]
A = [int(i) for i in input().split(' ')]
lst = []
for i in range(1,len(A) + 1):
    for c in combinations(A, i):
        lst.append(c)
#print(lst)
cnt = 0
for each in lst:
    for j in range(1,len(each) + 1):
        for c in combinations(each, j):
           if sum(c) == S:
                #print(c)
                cnt += 1
print(cnt % 998244353)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import itertools

def main():
  s = []
  read = stdin.readline
  N, S = map(int,read().split(" "))
  X = list(map(int,read().split(" ")))
  count = countm = 998244353
  for i in list(itertools.product([0,1], repeat = N)):
    if sum(i) == 0:
      continue
      
    else:
      sum_y = 0
      for j, k in zip(X,i):
        if j * k > S:
          break
        sum_y += j * k
      if sum_y == S:
        count -= (2**(N - sum(i))) 
        if count <= 0:
          count += countm

  print(countm - count)

    
  
  
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] += 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:
from sys import stdin
import itertools

def main():
  s = []
  read = stdin.readline
  N, S = map(int,read().split(" "))
  X = list(map(int,read().split(" ")))
  count = countm = 998244353
  for i in list(itertools.product([0,1], repeat = N)):
    if sum(i) == 0:
      continue
      
    else:
      y = [j*k for j, k in zip(X,i)]
      sum_y = sum(y)
      if sum_y == S:
        count -= (2**(N - sum(i))) 
        if count <= 0:
          count += countm

  print(countm - count)

    
  
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import itertools

def main():
  s = []
  read = stdin.readline
  N, S = map(int,read().split(" "))
  X = list(map(int,read().split(" ")))
  count = 0
  for i in list(itertools.product([0,1], repeat = N)):
    if sum(i) == 0:
      continue
      
    else:
      y = [j*k for j, k in zip(X,i)]
      sum_y = sum(y)
      if sum_y == S:
        count += (2**(N - sum(i))) 
  print(count%998244353)
    
  
  
if __name__ == "__main__":
  main()