結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
1