\(i\) 番目の数値が \(j\) になる組み合わせの数を \(C(i, j)\) とする.
このとき,
\[C(i+1, k) = \sum_{j=1}^{N/k} C(i, j)\]
となる. これを DP で計算すればいいのだが, 数値は最大で \(10^9\) なのでこのままではうまくいかない.
しかし, \(N/(k+1) \lt x \lt N/k\) については同一視しても構わないので, 状態数を \(\sqrt{N}\) に減らすことができるので, 上記の式の和の部分を累積和を使うことで間に合う.