とりあえず「簡単すぎる」ほうの問題を解く。$\mathrm{dp}[x][y] :=$商品を最初の$x$種類からちょうど$y$個選ぶ方法の総数、とする。$\mathrm{dp}[x][y] = d[x-1][y] + \mathrm{dp}[x-1][y-1] + ... + \mathrm{dp}[x-1][y-a_{x}]$と遷移できるが、これでは間に合わないので累積和を考える。つまり$\mathrm{DP}[x][y] :=$商品を最初の$x$種類から$y$個以下選ぶ方法の総数としたとき、
$$ \mathrm{DP}[x][y] = \mathrm{dp}[x][0]+ \mathrm{dp}[x][1] + ... + \mathrm{dp}[x][y] $$ $$ \mathrm{DP}[x][y] = \mathrm{DP}[x][y-1] + \mathrm{dp}[x][y] $$ $$ \mathrm{dp}[x][y] = \mathrm{DP}[x-1][y] - \mathrm{DP}[x-1][y-a_x-1] $$が成り立つので、
$$ \mathrm{DP}[x][y] = \mathrm{DP}[x][y-1] + \mathrm{DP}[x-1][y] - \mathrm{DP}[x-1][y-a_x-1] $$という${O}(1)$の遷移を導ける。ここから$y$を一個ずらした漸化式$\mathrm{DP}[x][y-1] = \mathrm{DP}[x][y-2] + \mathrm{DP}[x-1][y-1] - \mathrm{DP}[x-1][y-a_x-2]$を引くと、$\mathrm{dp}$についても同じ形の漸化式が得られる:
$$ \mathrm{dp}[x][y] = \mathrm{dp}[x][y-1] + \mathrm{dp}[x-1][y] - \mathrm{dp}[x-1][y-a_x-1] $$これで簡単なほうの問題が解けた。
さて、ここで$N$番目の商品と$i$番目の商品を入れ替えて同じDPをすることを考える。この配列を$\mathrm{dp}_i$とするとき、$\mathrm{dp}_i$は$\mathrm{dp}$と同じ遷移で求まり、しかも$N$種類の商品を処理すると同じ値になるはずである。つまり、任意の個数$y$について$\mathrm{dp}[N][y] = \mathrm{dp}_i[N][y]$が成り立つ。したがって
$$ \mathrm{dp}_i[N][y] = \mathrm{dp}_i[N][y-1] + \mathrm{dp}_i[N-1][y] - \mathrm{dp}_i[N-1][y-a_i-1] $$という等式から
$$ \mathrm{dp}[N][y] = \mathrm{dp}[N][y-1] + \mathrm{dp}_i[N-1][y] - \mathrm{dp}_i[N-1][y-a_i-1] $$が導け、整理すると
$$ \mathrm{dp}_i[N-1][y] = \mathrm{dp}[N][y] - \mathrm{dp}[N][y-1] + \mathrm{dp}_i[N-1][y-a_i-1] $$となる。$i$番目の商品を除いた場合に全体でちょうど$y$個の商品を選ぶ方法の総数を$f[i][y]$とするとき、$f[i][y] = \mathrm{dp}_i[N-1][y]$であるから、
$$ f[i][y] = \mathrm{dp}[N][y] - \mathrm{dp}[N][y-1] + f[i][y-a_i-1] $$となり、$f$についてDPすればクエリに${O}(1)$で答えられることになる。${O}(NM + Q)$。
戻すDPというらしい。
