結果

問題 No.269 見栄っ張りの募金活動
ユーザー startcppstartcpp
提出日時 2015-08-22 12:54:54
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,946 bytes
コンパイル時間 1,532 ms
コンパイル使用メモリ 52,196 KB
実行使用メモリ 19,292 KB
最終ジャッジ日時 2023-09-25 16:07:11
合計ジャッジ時間 2,983 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
権限があれば一括ダウンロードができます

ソースコード

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

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