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

Solution code:
def subsets(nums):
    output = []
    for i in range(1, len(nums)):
        backtrack(0, nums, i, [], output)

    return output


def backtrack(start, nums, size, curr, output):
    if len(curr) == size:
        output.append(curr[:])

    for i in range(start, len(nums)):
        curr.append(nums[i])
        backtrack(i + 1, nums, size, curr, output)
        curr.pop()


def count_subsets(num, sum):
    n = len(num)
    dp = [0 for _ in range(sum+1)]
    dp[0] = 1

    # with only one number, we can form a subset only when the required sum is equal to the number
    for s in range(1, sum+1):
        dp[s] = 1 if num[0] == s else 0

    # process all subsets for all sums
    for i in range(1, n):
        for s in range(sum, -1, -1):
            if s >= num[i]:
                dp[s] += dp[s - num[i]]

    return dp[-1]


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

result = count_subsets(sub_sets, S)

if result == 0:
    print(0)
    exit()

new_subsets = subsets(sub_sets)

result += sum(count_subsets(i, S) for i in new_subsets)

print(result % 998244353)

Submission status: Runtime Error

Solution code:
def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    while len(A) > 0:
        a = A[-1]
        if a > S:
            A.pop()
        else:
            break
    if len(A) == 0:
        return 0
    mod = 998244353
    n = len(A)
    l = [[0] * (n+1) for _ in range(S+1)]
    l[A[0]][1] = 1
    for i in range(1, n):
        for j in range(S, A[i]-1, -1):
            for k in range(1, n+1):
                l[j][k] += l[j-A[i]][k-1]
        l[A[i]][1] += 1
    r = 0
    for i in range(N):
        r += pow(2, N-i, mod) * l[-1][i]
        r %= mod
    return r
print(main())

Submission status: Runtime Error

Solution code:
def dfs(d,tot,num):
    global A,N,S,how
    if tot==S:
        how[num]+=1
        return
    if d==N:
        return
    if tot+A[d]<=S:
        dfs(d+1,tot+A[d],num+1)
    dfs(d+1,tot,num)
        
    

N,S=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
how=[0]*(N+1)
dfs(0,0,0)
cur=1
res=0
for i in range(N,0,-1):
    res+=how[i]*cur
    cur*=2
print(res)

Submission status: Runtime Error

Solution code:
def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    while len(A) > 0:
        a = A[-1]
        if a > S:
            A.pop()
        else:
            break
    if len(A) == 0:
        return 0
    mod = 998244353
    l = [[0] * (N+1) for _ in range(S+1)]
    l[A[0]][1] = 1
    for i in range(1, N):
        for j in range(S, A[i]-1, -1):
            for k in range(1, N+1):
                l[j][k] += l[j-A[i]][k-1]
        l[A[i]][1] += 1
    r = 0
    for i in range(N):
        r += pow(2, N-i, mod) * l[-1][i]
        r %= mod
    return r
print(main())

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=((ll)n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=((ll)a);i<((ll)n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (998244353ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1;for(auto s:t){os<<(a?"":" ")<<s;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

/*他のライブラリを入れる場所*/
int mpow(int v, ll a) {
    ll x = v, n = a, res = 1;
    while ( n ) {
        if ( n & 1 )res = res*x%MOD;
        x = x*x%MOD;
        n >>= 1;
    }
    return res;
}

class mint {
private:
    ll v;
public:
    static ll mod(ll a) { return ( a % MOD + MOD ) % MOD; }
    mint(ll a = 0) { this->v = mod(a); };
    mint(const mint &a) { v = a.v; }
    mint operator+(const mint &a) { return mint(v + a.v); }
    mint operator+(const ll a) { return mint(v + a % MOD); }
    mint operator+(const signed a) { return mint(v + a % MOD); }
    friend mint operator+(const ll a, const mint &b) { return mint(a % MOD + b.v); }
    void operator+=(const mint &a) { v = ( v + a.v ) % MOD; }
    void operator+=(const ll a) { v = mod(v + a % MOD); }
    void operator+=(const signed a) { v = mod(v + a % MOD); }
    friend void operator+=(ll &a, const mint &b) { a = mod(a % MOD + b.v); }
    mint operator-(const mint &a) { return mint(v - a.v); }
    mint operator-(const ll a) { return mint(v - a % MOD); }
    mint operator-(const signed a) { return mint(v - a % MOD); }
    friend mint operator-(const ll a, const mint &b) { return mint(a % MOD - b.v); }
    void operator-=(const mint &a) { v = mod(v - a.v); }
    void operator-=(const ll a) { v = mod(v - a % MOD); }
    void operator-=(const signed a) { v = mod(v - a % MOD); }
    friend void operator-=(ll &a, const mint &b) { a = mod(a % MOD - b.v); }
    mint operator*(const mint &a) { return mint(v * a.v); }
    mint operator*(const ll a) { return mint(v * ( a % MOD )); }
    mint operator*(const signed a) { return mint(v * ( a % MOD )); }
    friend mint operator*(const ll a, const mint &b) { return mint(a % MOD * b.v); }
    void operator*=(const mint &a) { v = ( v * a.v ) % MOD; }
    void operator*=(const ll a) { v = mod(v * ( a % MOD )); }
    void operator*=(const signed a) { v = mod(v * ( a % MOD )); }
    friend void operator*=(ll &a, const mint &b) { a = mod(a % MOD * b.v); }
    mint operator/(const mint &a);
    mint operator/(const ll a);
    mint operator/(const signed a);
    friend mint operator/(const ll a, const mint &b);
    void operator/=(const mint &a);
    void operator/=(const ll a);
    void operator/=(const signed a);
    friend void operator/=(ll &a, const mint &b);
    mint operator^(const mint &a) { return mpow(v, a.v); };
    mint operator^(const ll a) { return mpow(v, a); };
    mint operator^(const signed a) { return mpow(v, a); };
    friend mint operator^(const ll a, const mint &b) { return mpow(a, b.v); };
    void operator^=(const mint &a) { v = mpow(v, a.v); }
    void operator^=(const ll a) { v = mpow(v, a); }
    void operator^=(const signed a) { v = mpow(v, a); }
    mint operator+() { return *this; }
    mint operator++() { v++; return *this; }
    mint operator++(signed d) { mint res = *this; v++; return res;}
    mint operator-() { return operator*(-1); }
    mint operator--() { v--; return *this; }
    mint operator--(signed d) { mint res = *this; v--; return res;}
    bool operator==(mint &a) { return v == a.v; }
    bool operator==(signed a) { return v == a; }
    friend bool operator==(signed a, mint &b) { return a == b.v; }
    bool operator!=(mint &a) { return v != a.v; }
    bool operator!=(signed a) { return v != a; }
    friend bool operator!=(signed a, mint &b) { return a != b.v; }
    operator int() { return v; }
};
const int setModMax = 510000;
mint fac[setModMax], finv[setModMax], inv[setModMax];
void setMod() {
    fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1;
    for ( int i = 2; i < setModMax; i++ ) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * ( MOD / i ) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
mint minv(ll a) {
    if ( fac[0] == 0 )setMod();
    if ( a < setModMax ) return inv[a];
    a %= MOD;
    ll b = MOD, x = 1, y = 0;
    while ( b ) {
        ll t = a / b;
        a -= t*b; swap(a, b);
        x -= t*y; swap(x, y);
    }
    return ( x % MOD + MOD ) % MOD;
}

mint mint::operator/(const mint &a) { return mint(v * minv(a.v)); }
mint mint::operator/(const ll a) { return mint(v * minv(a)); }
mint mint::operator/(const signed a) { return mint(v * minv(a)); }
mint operator/(const ll a, const mint &b) { return mint(a % MOD * minv(b.v)); }
void mint::operator/=(const mint &a) { v = ( v * minv(a.v) ) % MOD; }
void mint::operator/=(const ll a) { v = mod(v * minv(a)); }
void mint::operator/=(const signed a) { v = mod(v * minv(a)); }
void operator/=(ll &a, const mint &b) { a = mint::mod(a % MOD * minv(b.v)); }
auto&operator>>(istream&is,mint&t){ll a; cin>>a; t=a; return is;};
auto&operator<<(ostream&os,mint&t){cout<<((int)t); return os;};
mint operator"" _m(unsigned long long a){return mint(a);}
using vm=vector<mint>;
using vvm=vector<vm>;
mint nCr(ll n,ll r){
    if ( fac[0] == 0 )setMod();
    return fac[n]*finv[r]*finv[n-r];
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,s;
    cin>>n>>s;
    vl a(n);cin>>a;
    vvm dp(2,vm(s+1,0));
    dp[0][0]=2_m^n;
    // mint ans=0;
    rep(i,n){
        dp[1-i%2]=dp[i%2];
        rep(j,s){
            if(j+a[i]>s)continue;
            dp[1-i%2][j+a[i]]+=dp[i%2][j]/2;
        }
        // puta(dp[i%2]);
        // ll d = dp[1-i%2][s]-dp[i%2][s];

    }
    puta(dp[n%2][s]);
    return 0;
}

Submission status: Runtime Error

Solution code:
from itertools import combinations

n, s = map(int,input().split())
a = list(map(int,input().split()))
counter = 0
subsets=[]
for i in range(n + 1):
    for c in combinations(a, i):
        subsets.append(c)

def dfs(i, sum, n, k, a):
    # n 個決め終わったら、今までの和 sum が k と等しいかを返す
    if i == n:
        return sum == k

    # a[i] を使わない場合
    if dfs(i + 1, sum):
        return True

    # a[i] を使う場合
    if dfs(i + 1, sum + a[i]):
        return True

    # a[i] を使う使わないに拘らず k が作れないので False を返す
    return False

for subset in subsets:
  if dfs(0, 0, len(subset), s, subset):
    counter += 1
    
print(counter)

Submission status: Runtime Error

Solution code:
N,S = map(int,input().split())
A = list(map(int,input().split()))
dp = [[[] for i in range(S+1)] for i in range(N+1)]
dp[0][0].append(0)
for i in range(1,N+1):
    a = A[i-1]
    for j in range(S-a+1):
        if len(dp[i-1][j]) != 0:
            for k in dp[i-1][j]:
                dp[i][j+a].append(k+1)
    for j in range(S+1):
        if len(dp[i-1][j]) != 0:
            for k in dp[i-1][j]:
                dp[i][j].append(k)
A = dp[10][10]
A.sort()
ans = 0
for a in A:
    x = N - a
    ans += 2**x
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n,s=map(int,input().split())
a=list(map(int,input().split()))
a.sort()

element=[]
for i,e in enumerate(a):
    tmp=[1]*(n-1-i)
    element.append(np.array([0,e]).reshape(-1,*tmp))

res=0
for e in element:
    res=res+e

combinations=np.argwhere(res==s)
# print(combinations)

ans=0
for c in combinations:
    addedNum=sum(c)
    if addedNum!=0:
        ans+=2**(n-addedNum)
print(ans)

Submission status: Runtime Error

Solution code:
n , s = map(int, input().split())
a = list(map(int,input().split()))
x=[]
y=[0]*n
N = 998244353

def dfs(now,sum):
    if sum == s:
        z=y.copy()
        x.append(z)
        return
    if now == n:
        return

    for i in range(2):
        if i==0:
            dfs(now+1,sum)
        if i==1:
            y[now]=1
            sum+=a[now]
            dfs(now+1,sum)
            y[now]=0
            sum-=a[now]

dfs(0,0)

ans = 0
for i in x:
    ans += pow(2,n-sum(i),N)
ans %= N
print(ans)

Submission status: Runtime Error

Solution code:
from math import factorial as fac
from functools import lru_cache

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


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


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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys

N,S, *A = map(int, sys.stdin.buffer.read().split())
mod = 998244353

answer = [0 for _ in range(S+1)]
power2 = 1

for j in range(N):
  a = A[j]
  answer_next = [2*answer[i] for i in range(S+1)]
  for i in range(a+1,S+1):
    answer_next[i] += answer[i-a]
  answer_next[a] += power2
  power2 = (2*power2)%mod
  answer = [answer_next[i]%mod for i in range(S+1)]

print(answer[S])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

MOD = 998244353  # type: int

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

def solve(N: int, S: int, A: "List[int]"):
    f = gen_f(N, A)
    return f(S, 0)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, S, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Runtime Error

Solution code:
import sys

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

n, s = nm()
a = nl()
mod = 998244353
dp = [0]*(s+1)
dp[0] = 1
for i in range(n):
    v = a[i]
    for j in range(s, -1, -1):
        dp[j] = (dp[j]*2 + dp[j-v]*(j >= v)) % mod
print(dp[s])

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,s,*a = map(int,read().split())

MOD = 998244353
def mul(c,m,dp): #multiply (2+x^c) up to x^m
    for i in range(m,c-1,-1):
        dp[i] *= 2
        dp[i] += dp[i-c]
        dp[i] %= MOD
    for i in range(c-1,-1,-1):
        dp[i] *= 2
        dp[i] %= MOD

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

for i in a:
    mul(i,s,dp)

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