結果

問題 No.42 貯金箱の溜息
ユーザー kimiyukikimiyuki
提出日時 2019-08-21 15:24:40
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 541 ms / 5,000 ms
コード長 3,225 bytes
コンパイル時間 2,450 ms
コンパイル使用メモリ 204,440 KB
実行使用メモリ 6,816 KB
最終ジャッジ日時 2024-10-09 02:55:33
合計ジャッジ時間 4,075 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
using namespace std;
template <typename X, typename T> auto make_vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto make_vectors(X x, Y y, Z z, Zs... zs) { auto cont = make_vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }


template <int32_t MOD>
struct mint {
    int32_t value;
    mint() : value() {}
    mint(int64_t value_) : value(value_ < 0 ? value_ % MOD + MOD : value_ >= MOD ? value_ % MOD : value_) {}
    inline mint<MOD> operator + (mint<MOD> other) const { int32_t c = this->value + other.value; return mint<MOD>(c >= MOD ? c - MOD : c); }
    inline mint<MOD> operator * (mint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return mint<MOD>(c < 0 ? c + MOD : c); }
    inline mint<MOD> & operator += (mint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline mint<MOD> & operator *= (mint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
};


template <typename T, size_t H, size_t W>
using matrix = array<array<T, W>, H>;
template <typename T, size_t A, size_t B, size_t C>
matrix<T, A, C> operator * (matrix<T, A, B> const & a, matrix<T, B, C> const & b) {
    matrix<T, A, C> c = {};
    REP (y, A) REP (z, B) REP (x, C) c[y][x] += a[y][z] * b[z][x];
    return c;
}
template <typename T, size_t H, size_t W>
array<T, H> operator * (matrix<T, H, W> const & a, array<T, W> const & b) {
    array<T, H> c = {};
    REP (y, H) REP (z, W) c[y] += a[y][z] * b[z];
    return c;
}
template <typename T, size_t N>
matrix<T, N, N> unit_matrix() {
    matrix<T, N, N> a = {};
    REP (i, N) a[i][i] = 1;
    return a;
}
template <typename T, size_t N>
matrix<T, N, N> powmat(matrix<T, N, N> x, int64_t k) {
    matrix<T, N, N> y = unit_matrix<T, N>();
    for (; k; k >>= 1) {
        if (k & 1) y = y * x;
        x = x * x;
    }
    return y;
}


constexpr int MOD = 1e9 + 9;
constexpr int SIZE = 6;
const array<int, SIZE> VALUE = { 1, 5, 10, 50, 100, 500 };
int main() {
    // prepare
    vector<array<array<mint<MOD>, SIZE>, SIZE> > dp(VALUE[SIZE - 1] + 1);
    REP (l, SIZE) {
        dp[0][l][l] = 1;
    }
    REP (a, dp.size()) REP (m, SIZE) REP3 (r, m, SIZE) {
        REP (l, m + 1) if (a + VALUE[l] < dp.size()) {
            dp[a + VALUE[l]][l][r] += dp[a][m][r];
        }
    }

    matrix<mint<MOD>, SIZE, SIZE> f = {};
    REP (y, SIZE) REP (x, SIZE) {
        f[y][x] = dp[VALUE[SIZE - 1]][y][x];
    }
    array<mint<MOD>, SIZE> x = {};
    x[SIZE - 1] = 1;

    auto solve1 = [&](int64_t m) {
        int64_t a = m / VALUE[SIZE - 1];
        int64_t b = m % VALUE[SIZE - 1];
        auto y = powmat(f, a) * x;
        mint<MOD> answer = 0;
        REP (l, SIZE) REP (r, SIZE) {
            answer += dp[b][l][r] * y[r];
        }
        return answer;
    };

    // query
    int t; cin >> t;
    while (t --) {
        int64_t m; cin >> m;
        cout << solve1(m).value << endl;
    }
    return 0;
}
0