P13659 [CERC 2020] Storage Problems

黑帮分子成功抢劫了城市中最著名的拍卖行。现在他们安全地藏身在他们的据点，并将偷来的物品存放在那里。幸运的是，你设法在他们的据点里安放了窃听器。你还拥有每个黑帮分子的个人档案，其中包含他们的声音录音。你将仔细监听接下来发生的事情，希望这能帮助你调查这起抢劫案。 每个黑帮分子恰好偷了一个物品，第 $i$ 个黑帮分子偷了第 $i$ 个物品。现在每个黑帮分子都试图把自己的物品放入公共储藏室，储藏室最多能承受总重量 $K$。储藏室是一个小房间，黑帮分子们依次存放他们的物品。 当某个黑帮分子试图将物品放入储藏室，但发现放不下时（即储藏室内物品的总重量加上他的新物品会超过 $K$），他会生气并把储藏室里的所有物品都扔出去。在此过程中，他会告诉其他人：“$j$ items are going to trash!”（$j$ 个物品要被扔掉了！），其中 $j$ 是他试图存放物品时储藏室中的物品数量。此时会发生争吵，之后不会再有物品被存放。 由于你在黑帮分子的储藏室里安放了窃听器，你会听到黑帮分子扔出多少物品。此外，利用你的个人档案，你可以分辨出每个黑帮分子的声音。 因此，如果你能提前知道，对于所有可能的 $j$ 和 $i$，在第 $i$ 个黑帮分子扔出所有 $j$ 个物品时，储藏室中可能存在多少种不同的物品子集，这将极大地帮助你的调查。由于子集的数量可能很大，请将结果对 $167772161$ 取模后输出。

输入包含两行。 第一行包含两个整数 $N$ 和 $K$（$2 \leq N \leq 400$，$1 \leq K \leq 400$），分别表示黑帮分子的数量和储藏室能承受的最大总重量。 第二行包含 $N$ 个整数 $w_1, w_2, \cdots, w_N$，其中 $1 \leq w_i \leq K$，表示第 $i$ 个黑帮分子偷的物品的重量。

输出共 $N$ 行，每行恰好包含 $N-1$ 个整数。第 $i$ 行的第 $j$ 个值表示：恰好包含 $j$ 个物品的子集，这些物品的总重量不超过 $K$，但无法再加入第 $i$ 个黑帮分子的物品（即加上 $w_i$ 后会超过 $K$）的子集数量。每个数对 $167772161$ 取模。

由 ChatGPT 4.1 翻译