結果

問題 No.42 貯金箱の溜息
ユーザー tottoripapertottoripaper
提出日時 2015-11-18 16:55:28
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,747 ms / 5,000 ms
コード長 2,356 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 28,920 KB
実行使用メモリ 4,352 KB
最終ジャッジ日時 2023-10-11 18:00:06
合計ジャッジ時間 7,574 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,630 ms
4,352 KB
testcase_01 AC 1,747 ms
4,348 KB
testcase_02 AC 1,744 ms
4,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>

typedef long long ll;

const ll MOD = 1e9 + 9;

int T;
ll M;

// dp2[i][j] := 和がjとなるような2未満の整数i個の組の数
ll dp2[30][30], dp5[30][30];

ll expt(ll a, ll n){
    ll res = 1ll;
    while(n > 0){
        if(n & 1){res = res * a % MOD;}
        n >>= 1;
        a = a * a % MOD;
    }
    return res;
}

ll nCk(ll n, ll k){
    if(n < 0 || k < 0 || n < k){return 0ll;}

    ll res = 1ll;
    for(ll i=n;i>n-k;i--){
        res = res * (i % MOD) % MOD;
    }

    for(ll i=1;i<=k;i++){
        res = res * expt(i, MOD-2) % MOD;
    }

    return res;
}

ll nHk(ll n, ll k){
    if(n == 0 && k == 0){return 1ll;}
    return nCk(n+k-1, k);
}

ll solve(){
    ll res = 0ll;
    
    for(int i1=0;i1<5;i1++){ // 1 (2, 5)
        for(int i5=0;i5<4;i5++){ // 5 (2)
            for(int i10=0;i10<15;i10++){ // 10 (5)
                for(int i50=0;i50<8;i50++){ // 50 (2)
                    for(int i100=0;i100<25;i100++){ // 100 (5)
                        ll diff = M - (1ll * i1 + i5 * 5 + i10 * 10 + i50 * 50 + i100 * 100);
                        if(diff < 0 || diff % 500 > 0){continue;}

                        // printf("%d, %d, %d, %d, %d: %lld %lld %lld %lld %lld %lld %lld; %lld\n", i1, i5, i10, i50, i100, dp5[1][i1], dp2[2][i5], dp5[3][i10], dp2[4][i50], dp5[5][i100], nHk(diff/500+1, 5), diff, dp5[1][i1] * dp2[2][i5] % MOD * dp5[3][i10] % MOD * dp2[4][i50] % MOD * dp5[5][i100] % MOD * nHk(diff/500+1, 5));
                        res = (res + dp5[1][i1] * dp2[2][i5] % MOD * dp5[3][i10] % MOD * dp2[4][i50] % MOD * dp5[5][i100] % MOD * nHk(diff/500+1, 5) % MOD) % MOD;               
                    }
                }
            }
        }
    }

    return res;
}

int main(){
    dp2[0][0] = 1ll;
    for(int i=1;i<30;i++){
        for(int j=0;j<30;j++){
            for(int k=0;k<2;k++){
                if(j-k < 0){continue;}
                dp2[i][j] = (dp2[i][j] + dp2[i-1][j-k]) % MOD;
            }

        }
    }

    dp5[0][0] = 1ll;
    for(int i=1;i<30;i++){
        for(int j=0;j<30;j++){
            for(int k=0;k<5;k++){
                if(j-k < 0){continue;}
                dp5[i][j] = (dp5[i][j] + dp5[i-1][j-k]) % MOD;
            }
        }
    }
    
    scanf("%d", &T);

    for(int i=0;i<T;i++){
        scanf("%lld", &M);

        printf("%lld\n", solve());
    }
}
0