$\#_p$ Subset Sum

AC一覧

Problem Statement
問題文

Given $N$ positive integers $s_0,s_1,\ldots,s_{N-1}$ and a positive integer $T$.

For each $t=1,2,...,T$, count the number of subset $I \subseteq \{0,1,...,N-1\}$ s.t. $\sum_{i \in I} s_i=t$ and print it $\bmod 998{,}244{,}353$ (we denote it as $p_t$).

$N$個の正整数 $s_0,s_1,\ldots,s_{N-1}$ と正整数 $T$ が与えられます。

$t=1,2,...,T$ について、部分集合 $I \subseteq \{0,1,...,N-1\}$ のうち$\sum_{i \in I} s_i=t$となるものの個数を $998{,}244{,}353$ で割った余り $p_t$ を求めてください。

Constraints
制約

Input
入力

$N$ $T$
$s_0$ $s_1$ ... $s_{N-1}$

Output
出力

$p_1$ $p_2$ ... $p_T$

Sample
サンプル

# 1

5 3
1 1 2 2 3
2 3 5 

Forum


Timelimit: 10 secs

Before submitting, please confirm terms and conditions