結果

問題 No.41 貯金箱の溜息（EASY）
ユーザー 古寺いろは古寺いろは
提出日時 2015-04-14 00:16:00
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,304 bytes
コンパイル時間 1,570 ms
コンパイル使用メモリ 170,760 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-04 14:19:11
合計ジャッジ時間 1,893 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;

long long mod = (long long)1e9 + 9;


vector<vector<long long>> fmatrix(int N){
    vector<vector<long long>> ret(N, vector<long long>(N));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i == j) ret[i][j] = 1;
            else ret[i][j] = 0;
        }
    }
    return ret;
}

vector<vector<vector<long long>>> mulboard;

vector<vector<long long>> matrixmul(vector<vector<long long>> v1){
    int N = v1.size();
    vector<vector<long long>> ret(N, vector<long long>(N));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            for (int k = 0; k < N; k++)
            {
                ret[i][j] += v1[i][k] * v1[k][j];
                if (k != 0) ret[i][j] -= v1[i][k - 1] * v1[k][j];
                ret[i][j] %= mod;
                ret[i][j] += mod;
                ret[i][j] %= mod;
            }
        }
    }
    return ret;
}

vector<int> cost;

#define MAX 500
long long dp[6][6][MAX + 1];

long long nowdp[6];
long long nextdp[6];

int main() {
    cost.push_back(1);
    cost.push_back(5);
    cost.push_back(10);
    cost.push_back(50);
    cost.push_back(100);
    cost.push_back(500);
    
    vector<vector<long long>> firstboard(6, vector<long long>(6));
    for (int t = cost.size() - 1; t >= 0; t--)
    {
        for (int i = 0; i < cost.size(); i++)
        {
            for (int j = 0; j <= MAX; j++)
            {
                dp[t][i][j] = 0;
            }
        }
        dp[t][t][0] = 1;

        for (int i = 0; i < cost.size(); i++)
        {
            for (int j = 0; j <= MAX; j++)
            {
                if (i > 0) dp[t][i][j] += dp[t][i - 1][j];
                if (j >= cost[i]) dp[t][i][j] += dp[t][i][j - cost[i]];
                dp[t][i][j] %= mod;
            }
        }

        for (int i = 0; i < cost.size(); i++)
        {
            firstboard[t][i] = dp[t][i][MAX];
        }
    }

    auto nowboard = firstboard;
    mulboard.push_back(nowboard);
    for (int i = 0; i < 62; i++)
    {
        nowboard = matrixmul(nowboard);
        mulboard.push_back(nowboard);
    }

    int T;
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        long long M;
        cin >> M;
        long long p = M / MAX;
        for (int j = 0; j < 6; j++)
        {
            nowdp[j] = 0;
            nextdp[j] = 0;
        }
        for (int j = 0; j < 6; j++)
        {
            nowdp[j] = dp[0][j][M%MAX];
        }

        int count = 0;
        while (p > 0){
            if (p % 2 == 1){
                for (int i = 0; i < 6; i++)
                {
                    for (int j = 0; j < 6; j++)
                    {
                        nextdp[j] += nowdp[i] * mulboard[count][i][j];
                        if (i != 0)
                            nextdp[j] -= nowdp[i - 1] * mulboard[count][i][j];
                    }
                }

                for (int j = 0; j < 6; j++)
                {
                    nowdp[j] = nextdp[j] % mod;
                    if (nowdp[j] < 0) nowdp[j] += mod;
                    nextdp[j] = 0;
                }
            }
            count++;
            p /= 2;
        }

        long ans = nowdp[5] % mod;
        cout << ans << endl;
    }
}
0