ABC221-H Counting Multiset ヤング図形で考察する

atcoder.jp
を解きたいです。整数の分割の数え上げですね。問題の条件を満たす整数の分割に対し、ヤング図形の転置を考えると、以下の条件を満たす整数 $N$ の分割 $(\lambda_1,\lambda_2,\dots,\lambda_l) \ (\lambda_1 \geq \lambda_2 \geq \dots)$ の数え上げになります。
・ $\lambda_1=k$
・ $\lambda_i-\lambda_{i+1} \leq M$
これの数え上げはdp[i][j] := $\lambdaの総和がi,\lambda_1=j$ として解くことができます。明らかな漸化式から累積和dpを導出することもできますが、 $\lambda_1=j-1$ である分割をとり $\lambda_1$ を $j$ に書き換えることを考えると、 $\lambda_2=j-M-1$ であるようなものを余分に数えていて、逆にこれを除けば $\lambda_1=j$ かつ $\lambda_2 \neq j$ であるような分割を全て数えられているので、漸化式
dp[i][j]=dp[i-1][j-1]-dp[i-j][j-M-1]+dp[i-j][j]
を得ることができ、累積和なしでも解けます。(上記の漸化式は、noshiさんのユーザー解説やkanpurinさんのユーザー解説に載っているものと同じです)