結果

問題 No.42 貯金箱の溜息
ユーザー krotonkroton
提出日時 2014-10-17 04:10:40
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 25 ms / 5,000 ms
コード長 2,894 bytes
コンパイル時間 893 ms
コンパイル使用メモリ 81,652 KB
実行使用メモリ 6,940 KB
最終ジャッジ日時 2024-06-09 16:12:49
合計ジャッジ時間 1,348 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 20 ms
6,812 KB
testcase_01 AC 25 ms
6,940 KB
testcase_02 AC 23 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <fstream>
#include <sstream>
using namespace std;
typedef long long ll;

const ll MOD = 1000000009ll;

int coin[] = {1, 5, 10, 50, 100, 500};

ll dp[3010];
vector<ll> coef[510];

ll mod_pow(ll x, ll e){
    ll v = 1;
    for(;e;e>>=1){
        if(e & 1)v = (v * x) % MOD;
        x = (x * x) % MOD;
    }
    return v;
}

vector<ll> gauss(vector< vector<ll> > A, vector<ll> b){
    const int size = (int)A.size();
    vector< vector<ll> > M(size, vector<ll>(size + 1));
    
    for(int i=0;i<size;i++){
        for(int j=0;j<size;j++){
            M[i][j] = A[i][j];
        }
        M[i][size] = b[i];
    }
    
    for(int i=0;i<size;i++){
        int p = -1;
        for(int j=i;j<size;j++){
            if(M[j][i] != 0){
                p = j;
                break;
            }
        }
        swap(M[i], M[p]);
        
        ll inv = mod_pow(M[i][i], MOD - 2);
        for(int j=i;j<=size;j++){
            M[i][j] *= inv;
            M[i][j] %= MOD;
        }
        
        for(int j=i+1;j<size;j++){
            ll p = M[j][i];
            for(int k=i;k<=size;k++){
                M[j][k] -= p * M[i][k] % MOD;
                M[j][k] = (M[j][k] + MOD) % MOD;
            }
        }
    }
    
    for(int i=size-1;i>=0;i--){
        ll inv = mod_pow(M[i][i], MOD - 2);
        M[i][size] *= inv;
        M[i][size] %= MOD;
        
        ll now = M[i][size];
        for(int j=0;j<i;j++){
            M[j][size] -= M[j][i] * now % MOD;
            M[j][size] = (M[j][size] + MOD) % MOD;
        }
    }
    
    vector<ll> x(size);
    for(int i=0;i<size;i++)x[i] = M[i][size];
    
    return x;
}

void initCoef(int m){
    vector< vector<ll> > A(6, vector<ll>(6, 0));
    vector<ll> b(6);
    for(int x=0;x<6;x++){
        ll p = 1;
        for(int i=0;i<6;i++){
            A[x][i] = p;
            p *= x;
            p %= MOD;
        }
        b[x] = dp[500 * x + m];
    }
    coef[m] = gauss(A, b);
}

void init(){
    const int N = 3000;

    dp[0] = 1;
    for(int i=0;i<6;i++){
        for(int sum=coin[i];sum<=N;sum++){
            dp[sum] = (dp[sum] + dp[sum - coin[i]]) % MOD;
        }
    }
    
    for(int i=0;i<500;i++)initCoef(i);
}

ll solve(ll M){
    ll res = 0;
    
    ll x = (M / 500) % MOD;
    ll m = M % 500;
    
    ll p = 1;
    for(int i=0;i<6;i++){
        res = (res + p * coef[m][i] % MOD) % MOD;
        p *= x;
        p %= MOD;
    }
    
    return res;
}

int main(){
    init();
    
    int T;
    cin >> T;
    
    while(T--){
        ll M;
        cin >> M;
        
        cout << solve(M) << endl;
    }
    
    return 0;
}
0