問題
$N$ 個の品物があり、品物 $i$ の重さは $w_i$。各 $i=1,\dots,N$ について次の値を求めよ。
品物 $i$ 以外 の $N-1$ 個から部分集合を選び、重さの合計がちょうど $W$ になる選び方の数（998244353 で割った余り）
品物は重さが同じでも区別する。空集合も部分集合に含める（$W\ge1$ なので答えには効かない）。
入力形式
N W
w_1 w_2 ... w_N制約
| # | 条件 |
|---|---|
| 1 | $1\le N\le 2000$ |
| 2 | $1\le W\le 2000$ |
| 3 | $1\le w_i\le 10^9$ |
入出力例
入力例1
6 10
1 2 3 4 5 6出力例1
2
3
2
2
3
3入力例2
4 5
1 2 3 4出力例2
1
1
1
1（例1: 全体で和が 10 になる部分集合は $\{4,6\},\{1,3,6\},\{1,4,5\},\{2,3,5\},\{1,2,3,4\}$ の 5 個。品物 1（重さ 1）を除くと $\{4,6\},\{2,3,5\}$ の 2 個、品物 2 を除くと $\{4,6\},\{1,3,6\},\{1,4,5\}$ の 3 個）
概念図：戻す DP の向き
ヒント（クリックで段階的に開示）
ヒント1（方向性）
品物 $i$ ごとに DP を作り直すと $O(N^2W)$。$N=W=2000$ で $8\times10^9$ 回の更新になる（実測で $N=W=1000$ でも 70.9 s）。全員分の表 $f$ を 1 回作り、そこから品物 $i$ の寄与だけを「取り消す」ことを考える。
ヒント2（アプローチ）
部分和の数え上げ表 $f$ は多項式 $F(x)=\prod_i(1+x^{w_i})$ の係数。品物 $i$ を除いた表 $g$ は $G(x)=F(x)/(1+x^{w_i})$。割る式は定数項が 1 なので、係数を小さい次数から順に決められる。
ヒント3（誘導）
$F=G\cdot(1+x^w)$ の係数を比べると $f[s]=g[s]+g[s-w]$。よって
g = f[:]
for s in range(w, W + 1): # 小さい s から: g[s-w] は既に「戻した後」の値
g[s] = (g[s] - g[s - w]) % MOD追加のループ（大きい $s$ から）と 向きが逆 になる。
模範解答 (Python)
模範解答を表示する（まず自力で解いてから）
import sys
MOD = 998244353
def main():
data = sys.stdin.buffer.read().split()
n, W = int(data[0]), int(data[1])
w = list(map(int, data[2:2 + n]))
# 1) 全品物での数え上げ f[s] = 和が s になる部分集合の数（多項式 Π(1+x^{w_i}) の係数）
f = [0] * (W + 1)
f[0] = 1
for wi in w:
if wi > W:
continue # W を超える品物は和 W に使えない（掛けても係数は変わらない）
for s in range(W, wi - 1, -1): # 大きい s から: 同じ品物を 2 回使わない
f[s] = (f[s] + f[s - wi]) % MOD
# 2) 品物 i を「戻す」: g * (1+x^{w_i}) = f ⇒ g[s] = f[s] - g[s-w_i]（小さい s から）
out = []
for wi in w:
if wi > W:
out.append(f[W])
continue
g = f[:]
for s in range(wi, W + 1):
g[s] = (g[s] - g[s - wi]) % MOD
out.append(g[W])
print("\n".join(map(str, out)))
main()計算量: 表の作成 $O(NW)$、各品物の取り消し $O(W)$、合計 $O(NW)$。実測で $N=W=2000$ が 0.53 s。
Step-by-Step 解説
「品物 $i$ を選ぶ／選ばない」は $(1+x^{w_i})$ を掛けることに当たる。$x^s$ の係数が「和が $s$ の選び方の数」。追加のループを大きい $s$ から回すのは、同じ品物を 2 回掛けないため（小さい $s$ からだと $(1+x^w+x^{2w}+\dots)$ を掛けたことになり、個数制限なしのナップサックになる）。
$F=G(1+x^w)$ の $x^s$ の係数は $f[s]=g[s]+g[s-w]$（$s<w$ なら $g[s-w]=0$）。$s$ の小さい順に $g[s]=f[s]-g[s-w]$ で一意に決まる。割る多項式 $1+x^w$ の定数項が 1 なので 逆元は要らない。$\bmod p$ のもとでも整数のときと同じ式がそのまま成り立つ。
追加は「大きい $s$ から」、取り消しは「小さい $s$ から」。取り消しで大きい方から回すと、$g[s-w]$ にまだ取り消し前の $f$ の値が入ったまま引いてしまう。実測で 300 ケース中 173 ケースが誤答になった。
取り消しは「掛けた多項式で割る」ことで、数え上げ（和と積）では逆演算がある。最大値を求める DP（価値最大のナップサック）では戻せない: $\max$ には逆演算が無く、たとえば重さ 1・価値 1 の品物を追加した後の表 $f=[0,1]$ は、追加前の表が $[0,0]$ でも $[0,1]$ でも同じになる（どちらも $f[1]=\max(g[1],g[0]+1)=1$）。削除が要る最大化は Day158-Q5 の時間軸セグメント木のように「追加だけで済むように並べ替える」。
| $N=W$ | 戻す DP | 作り直し $O(N^2W)$ |
|---|---|---|
| 300 | 0.06 s | 2.27 s |
| 1000 | 0.19 s | 70.9 s |
| 2000 | 0.53 s | 未計測（約 9〜10 分と見積もり） |
迷った他案と採らなかった理由
| 案 | 計算量 | 採否 | 理由 |
|---|---|---|---|
| 品物ごとに作り直す | $O(N^2W)$ | 検算用のみ | $N=W=1000$ で 70.9 s（実測） |
| 前からの表と後ろからの表を持ち、品物 $i$ の前後を畳み込む | $O(NW)$ 前計算 ＋ 各 $i$ で $O(W)$（和 $W$ の 1 係数だけなら） | 不採用 | 最大化 DP でも使える汎用の方法だが、表を $2N$ 本（$O(NW)$ メモリ、$N=W=2000$ で 800 万要素）持つ。数え上げなら戻す DP は $O(W)$ メモリで済む |
| 分割統治（左半分を足して右へ、右半分を足して左へ再帰） | $O(NW\log N)$ | 不採用 | 最大化にも使え、メモリも $O(W\log N)$。数え上げでは $\log N$ 倍遅いだけ |
| 戻す DP（本解） | $O(NW)$、メモリ $O(W)$ | 採用 | 数え上げ（逆演算のある演算）に限って最速 |
前提が変わったら:
- 重さ 0 の品物 を許すと $(1+x^0)=2$ で割ることになり、$2$ の逆元を掛ける必要がある（998244353 は奇素数なので可能）。法が $2^{64}$ などなら割れない
- 確率の DP（品物 $i$ を確率 $p_i$ で選ぶ）では $(1-p_i)+p_ix^{w_i}$ で割る。定数項 $1-p_i$ が 0 に近いと数値的に不安定になり、$p_i=1$ では割れない
- 最大化・最小化 の DP では戻せない（Step 4）。前後の表か分割統治を使う
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 取り消しを大きい $s$ から回す | $g[s-w]$ に取り消し前の値が残る | 小さい $s$ から（実測で 300 中 173 ケース誤答） |
引き算の後に % MOD をしない | Python では負の数のまま残り、次の引き算で壊れる（C++ ならオーバーフロー） | (g[s] - g[s-w]) % MOD |
| $w_i>W$ の品物を添字計算にそのまま使う | 固定長配列の言語では範囲外参照（Python は range が空になり偶然動く） | $w_i>W$ は表を変えない品物として明示的に飛ばし、答えは $f[W]$ |
| $f$ を上書きして取り消す | 次の品物の取り消しで元の表が要る | g = f[:] でコピー |
| 最大価値ナップサックで同じことをする | $\max$ に逆演算が無い | 前後の表・分割統治・時間軸セグ木 |
次のステップ
- 発展1: 「品物 $i$ と $j$ の両方を除いた」答えを $Q$ 個のクエリで求める（2 回割る。$O(QW)$）
- 発展2: 個数制限なしナップサックで品物を 1 種類除く（掛けたのは $1/(1-x^w)$ なので、取り消しは $(1-x^w)$ を掛ける＝$g[s]=f[s]-f[s-w]$ を大きい $s$ から）
- 扱わなかった範囲: 形式的冪級数の $\log$／$\exp$ を使って $\prod(1+x^{w_i})$ を $O(W\log W)$ で求める方法（本問は $O(NW)$ で十分）
検証ログ（本セッションで実行した数値）
- 全探索との一致（実測）: $N\le11$、$W\le25$ のランダム 300 ケースで、プログラム全体（標準入出力）の出力が部分集合の全列挙と全件一致
- 取り消しの向きを逆にした誤り（実測）: 同じ条件の 300 ケース中 173 ケースで不一致
- 作り直し版との一致と時間（実測）: $N=W=300$ で 0.06 s vs 2.27 s、$N=W=1000$ で 0.19 s vs 70.9 s（出力は全件一致）、$N=W=2000$ の本解 0.53 s
- 入力例1・2 の出力を実行で確認（
2 3 2 2 3 3、1 1 1 1） - 最大化で戻せない例（導出）: 重さ 1・価値 1 の品物について、追加前 $[0,0]$ と $[0,1]$ が同じ $[0,1]$ になる
- 出所ラベル: 数値は実測（Python 3.14.7）。$N=W=2000$ の作り直し版の時間は $1000$ の結果を 8 倍した見積もり
- 検証スクリプト: スクラッチパッドの
d161/q4.py・q4_test.py・q4_bench.py