(K-x).downto(0){|i| ds[i+x] += ds[i] })があえての降順なのはなぜか。今ループの遷移結果に対して再帰的に遷移操作を施してはいけないからだ。+x 操作が 0 を x に移すのも x を 2x に移すのもいいが、0 から移ってきた x を 2x に移すのはやりすぎ。DP 配列を遷移回数と同じだけ用意して退屈なコピー操作を書くのもひとつの方法だけど、ループを逆順にして書き込む前に読み込むことを確実にするのも手。巻き戻しをするときはそのような工夫が通用しない。すでに遷移が済んだあとの場合の数から、最終ループで加算した場合の数を求めて引き算しなければいけない。■提出 #46049349 (AC / 276 Byte / 1183 ms)。なんというか、きれいにはまって驚くんだけど、ループを昇順にすることで巻き戻しと再帰的な影響を取り除くことが同時にできる。■「この手の場合の数は母関数です。y^K の係数が場合の数です」というような内容をいくつか読んだけど、残念なことにそれはすでに武器を持っている人にしか役立てられない情報なのだな。(1+x)^N なら x^K の係数は自分でもコンビネーションで求められるけど、今回のように x の部分が何乗なのかいろいろな場合に、いろいろ掛けた結果 x が K 乗になるものがいくつあるのか知りたいとなっても、それこそ DP をして求めるしか方法を知らない。そしてそれができたら今回の問題は解けている。つまり「形式的べき級数解説 | maspyのHP」という武器を持っていない人間にとって言い換えはただの言い換えであって答えには近づいていない。残念だなあ。理解できないんだもんなあ。