/*考察フェーズ ・問題言い換え:A[1] + A[2] + … + A[N] = S, A[i+1] >= A[i] + K, A[0] >= 0を満たす整数列Aの個数を求めよ。 ・同値な問題 :A[1] + A[2] + … + A[N] = S - KN(N-1)/2, A[i+1] >= A[i], A[0] >= 0を満たす整数列Aの個数を求めよ。 ・大きさNの広義単調増加な非負整数列のうち、合計値がMであるものの個数をF(N, M)とすると、 F(N, M) = F(N-1, M) + F(N-1, M-1) + … + F(N-1, 0) とな…らないね!?(A[i+1] >= 0という条件なら簡単なのに…) ・A[i]を決める。A[i+1] >= 0という条件に変換したとき、同値な問題はどうなるか… →A[i+1]~A[N]の値が全て-A[i]される →(N - i - 1) * A[i]だけ合計値を減らしたものになる。 ・A[i] + A[i+1] + … + A[N] = M, A[i+1] >= A[i], A[j+1] >= A[j] ⇔ A[i+1] + … + A[N] = M - (N - i) * A[i], A[i+1] >= 0, A[j+1] >= A[j] ・これより、 F(N, M) = F(N-1, M) + F(N-1, M - N) + F(N-1, M - 2N) + … + F(N-1, M - CN) (Cは、M - CN >= 0を満たす整数の最大値) となる。 ・さらに F(N, M) = F(N, M-N) + F(N-1, M) とでき、高速化が可能。 ・「前に決めた値」を保持しなくても良くなった(「前に決めた値」が常に0だとした場合の問題に漸化式的に置換) ・状態数は、O(NS). 遷移は、O(1)→計算量O(NS). */ //実装フェーズ(→↓↑→→↓→→↑↑↓↓←→←→) #include using namespace std; int n, s, k; long long f[101][20001]; long long F(int N, int M) { if (N < 0 || M < 0) return 0; return f[N][M]; } int main() { cin >> n >> s >> k; s -= k * n * (n - 1)/2; f[0][0] = 1; for( int N = 1; N <= n; N++ ){ //残り項数 for( int M = 0; M <= s; M++ ){ //残り値 f[N][M] = F(N, M-N) + F(N-1, M); f[N][M] %= 1000000007; } } cout << F(n, s) << endl; return 0; }