3824. 完全背包计数

【题目描述】

你有 $n$ 个物品，第 $i$ 个物品的体积为 $v_i$，有无限件。给定 $m$，对于所有 $s\in [1,m]$，求选择物品恰好装满总体积为 $s$ 的背包的方案数。

【输入格式】

第一行两个整数 $n,m$。

第二行 $n$ 个正整数，第 $i$ 个表示 $v_i$。

【输出格式】

一个整数表示答案。答案对 $998244353$ 取模。

【样例输入】

2 4
1 2

【样例输出】

1
2
2
3

【数据规模与约定】

$1 \leq n,m \leq 10^5$。

$1 \leq v_i \leq m$

【来源】

生成函数的运算与组合计数问题——杭州学军中学——金策——2015CTS论文相关