結果
問題 | No.42 貯金箱の溜息 |
ユーザー | tottoripaper |
提出日時 | 2015-11-27 21:53:05 |
言語 | C++11 (gcc 11.4.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,561 bytes |
コンパイル時間 | 243 ms |
コンパイル使用メモリ | 29,184 KB |
実行使用メモリ | 11,420 KB |
最終ジャッジ日時 | 2023-10-11 23:17:07 |
合計ジャッジ時間 | 12,755 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | -- | - |
testcase_02 | -- | - |
ソースコード
#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) for(int i10=(M-i1-i5*5)%50/10;i10<50;i10+=5){ // 10 (5) for(int i50=(M-i1-i5*5-i10*10)%100/50;i50<10;i50+=2){ // 50 (2) 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(i1 < 0 || i5 < 0 || i10 < 0 || i50 < 0 || 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()); } }