$\#_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制約

• $1 \leq N \leq 10^{6}$
• $1 \leq T \leq 500{,}000$
• $1 \leq s_i \leq T$

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

Timelimit: 10 secs

Before submitting, please confirm terms and conditions