結果

問題 No.269 見栄っ張りの募金活動
ユーザー startcppstartcpp
提出日時 2015-08-22 12:02:52
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 644 ms / 5,000 ms
コード長 2,021 bytes
コンパイル時間 425 ms
コンパイル使用メモリ 54,368 KB
実行使用メモリ 18,816 KB
最終ジャッジ日時 2024-07-16 01:33:07
合計ジャッジ時間 3,309 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 4 ms
5,376 KB
testcase_04 AC 446 ms
8,960 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 644 ms
18,816 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 202 ms
5,376 KB
testcase_12 AC 1 ms
5,376 KB
testcase_13 AC 92 ms
5,376 KB
testcase_14 AC 159 ms
5,376 KB
testcase_15 AC 129 ms
5,376 KB
testcase_16 AC 1 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 137 ms
8,832 KB
testcase_19 AC 45 ms
5,376 KB
testcase_20 AC 32 ms
5,376 KB
testcase_21 AC 139 ms
5,376 KB
testcase_22 AC 32 ms
5,376 KB
testcase_23 AC 3 ms
5,376 KB
testcase_24 AC 86 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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

//実装フェーズ(→↓↑→→↓→→↑↑↓↓←→←→)
#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