和だけが重要なので，\(|U|\) は dp の状態として持っておく必要がない． \(dp_{i,x} := \) \(a_{[0,i)}\) において， \(\emptyset \neq U \subset T \subset N\) となる \(U,T\) のとり方であって， \(sum(a_{U}) = x\) となるものの個数
とする．遷移は，
- \(a_{i} \in U\) のとき： \(dp_{i+1, x+a_{i}} += dp_{i,x}\) .
- それ以外のとき： \(a_{i}\) が \(T\) に入るか入らないかの2択であるから， \(dp_{i+1, x} += 2 dp_{i,x}\)
これを inline で高速化すると，
- \(dp^{\prime}_{i+1, x+a_{i}} += dp^{\prime}_{i,x}\ \),
- \(dp^{\prime}_{i+1, x} += dp^{\prime}_{i,x}\) .
この時点で \(O(SN)\) であるから十分間に合うが， さらに inline にすると，
- \(dp^{\prime\prime}_{x+a_{i}} += dp^{\prime\prime}_{x}\ \),
- \(dp^{\prime\prime}_{x} += dp^{\prime\prime}_{x}\) .
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, s ;
cin >> n >> s;
vll a(n); rep(i,n) { cin >> a[i]; }
dp[0] = 1;
rep(i,n){
// vector<mint> old(s+1);
// swap(old, dp);
drep(x,s+1){
ll y = x + a[i];
// if(y <= s) dp[y] += old[x];
// dp[x] += mint(2)*old[x];
if(y <= s) dp[y] += dp[x];
dp[x] += dp[x];
}
}
cout << dp[s].val() << endl;
return 0;
}
