結果

問題 No.42 貯金箱の溜息
コンテスト
ユーザー tottoripaper
提出日時 2015-11-27 21:54:36
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,635 bytes
コンパイル時間 211 ms
コンパイル使用メモリ 25,216 KB
実行使用メモリ 8,352 KB
最終ジャッジ日時 2024-09-13 23:26:38
合計ジャッジ時間 12,723 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:67:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   67 |     scanf("%d", &T);
      |     ~~~~~^~~~~~~~~~
main.cpp:70:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   70 |         scanf("%lld", &M);
      |         ~~~~~^~~~~~~~~~~~

ソースコード

diff # 

#include <cstdio>

typedef long long ll;

const ll MOD = 1e9 + 9;

int T;
ll M;

ll perm_inv[7];

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 = i % MOD * res % MOD;
    }

    return res * perm_inv[k] % MOD;
}

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=M%5;i1<500;i1+=5){
        for(int i5=(M-i1)%10/5;i5<100;i5+=2){ // 5 (2)
            if(i5 < 0){continue;}
            for(int i10=(M-i1-i5*5)%50/10;i10<50;i10+=5){ // 10 (5)
                if(i10 < 0){continue;}
                for(int i50=(M-i1-i5*5-i10*10)%100/50;i50<10;i50+=2){ // 50 (2)
                    if(i50 < 0){continue;}
                    int i100 = (M-i1-i5*5-i10*10-i50*50)%500/100;
                    ll diff = M - (1ll * i1 + i5 * 5 + i10 * 10 + i50 * 50 + i100 * 100);
                    if(i100 < 0 || diff < 0){continue;}
                    // printf("%d, %d, %d, %d, %d: %lld\n", i1, i5, i10, i50, i100, nHk(diff/500+1, 5));
                    res = (res + nHk(diff/500+1, 5)) % MOD;               
                }
            }
        }
    }

    return res;
}

int main(){
    perm_inv[0] = 1;
    for(int i=1;i<=6;i++){
        perm_inv[i] = perm_inv[i-1] * expt(i, MOD-2) % MOD;
    }
    
    scanf("%d", &T);

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

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