No.269

$i$ 番目の生徒が $j$ 円寄付するとき, $i + 1$ 番目以降の生徒も $j + K$ 円したとみなし, $i$ 番目の生徒が前の生徒より $a_i$ 円多く寄付したとすると,

$$\begin{align} S &= (a_1 + (n-1)(a_1+K)) + (a_2 + (n-2)(a_2+K)) + \dots + a_N \\ &= na_1 + (n-1)a_2 + \dots + a_N + K\sum_{i=1}^{N-1} \\ &= na_1 + (n-1)a_2 + \dots + a_N + KN(N-1)/2 \end{align}$$

となる. $S^{\prime} = S - KN(N-1)/2$ とすると,

$$S^{\prime} = na_1 + (n-1)a_2 + \dots a_N$$

となる組み合わせの数を求める問題となる.

$i$ 番目まで見たときに合計が $j$ になる組み合わせの数を $A(i, j)$ とすると,

$$A(i, j) = A(i-1, j) + A(i, j-(N-i))$$

という漸化式になるので, これを DP で計算する.