結果

問題 No.42 貯金箱の溜息
ユーザー tottoripaper
提出日時 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);
      |         ~~~~~^~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <cstdio>
typedef long long ll;
const ll MOD = 1e9 + 9;
int T;
ll M;
// dp2[i][j] := j2i
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());
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0