結果
問題 | No.42 貯金箱の溜息 |
ユーザー | tottoripaper |
提出日時 | 2015-11-20 15:57:03 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 46 ms / 5,000 ms |
コード長 | 2,057 bytes |
コンパイル時間 | 1,390 ms |
コンパイル使用メモリ | 29,268 KB |
実行使用メモリ | 4,352 KB |
最終ジャッジ日時 | 2023-10-11 18:09:09 |
合計ジャッジ時間 | 955 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
4,348 KB |
testcase_01 | AC | 46 ms
4,348 KB |
testcase_02 | AC | 45 ms
4,352 KB |
ソースコード
#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 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; int i1 = M % 5; for(int i5=(M-i1)%10/5;i5<4;i5+=2){ // 5 (2) for(int i10=(M-i1-i5*5)%50/10;i10<15;i10+=5){ // 10 (5) for(int i50=(M-i1-i5*5-i10*10)%100/50;i50<8;i50+=2){ // 50 (2) for(int i100=(M-i1-i5*5-i10*10-i50*50)%500/100;i100<25;i100+=5){ // 100 (5) ll diff = M - (1ll * i1 + i5 * 5 + i10 * 10 + i50 * 50 + i100 * 100); 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(){ perm_inv[0] = 1; for(int i=1;i<=6;i++){ perm_inv[i] = perm_inv[i-1] * expt(i, MOD-2) % MOD; } 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()); } }