結果

問題 No.269 見栄っ張りの募金活動
コンテスト
ユーザー startcpp
提出日時 2015-08-22 11:54:56
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 639 ms / 5,000 ms
コード長 2,021 bytes
コンパイル時間 488 ms
コンパイル使用メモリ 55,116 KB
実行使用メモリ 18,944 KB
最終ジャッジ日時 2024-07-16 01:32:25
合計ジャッジ時間 3,304 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*考察フェーズ
・問題言い換え：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[j+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-1) + ？
  とでき、高速化が可能…といいたかったが、？が分からないので終了。
  
・「前に決めた値」を保持しなくても良くなった（「前に決めた値」が常に0だとした場合の問題に漸化式的に置換）
・状態数は、O(NS). 遷移は、ならしO(logN)→計算量O(NSlogN).
*/

//実装フェーズ(→↓↑→→↓→→↑↑↓↓←→←→)
#include<iostream>
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++ ){	//残り値
			for( int C = 0; M - C * N >= 0; C++ ){
				f[N][M] += F(N-1, M - C * N);
			}
			f[N][M] %= 1000000007;
		}
	}
	cout << F(n, s) << endl;
	return 0;
}
0