結果
問題 | No.42 貯金箱の溜息 |
ユーザー |
![]() |
提出日時 | 2015-11-18 16:55:28 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2,075 ms / 5,000 ms |
コード長 | 2,356 bytes |
コンパイル時間 | 312 ms |
コンパイル使用メモリ | 25,856 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-13 16:58:19 |
合計ジャッジ時間 | 8,760 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:87:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 87 | scanf("%d", &T); | ~~~~~^~~~~~~~~~ main.cpp:90:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 90 | scanf("%lld", &M); | ~~~~~^~~~~~~~~~~~
ソースコード
#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());}}