結果

問題 No.42 貯金箱の溜息
ユーザー kimiyukikimiyuki
提出日時 2019-08-21 14:53:53
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 534 ms / 5,000 ms
コード長 5,270 bytes
コンパイル時間 2,209 ms
コンパイル使用メモリ 204,968 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-08 22:27:31
合計ジャッジ時間 3,995 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 53 ms
6,820 KB
testcase_01 AC 534 ms
6,820 KB
testcase_02 AC 484 ms
6,820 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 = this->value - other.value; return mint<MOD>(c <    0 ? 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 -= other.value; if (this->value <    0) 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; }
    inline mint<MOD> operator - () const { return mint<MOD>(this->value ? MOD - this->value : 0); }
    mint<MOD> pow(uint64_t k) const {
        mint<MOD> x = *this, y = 1;
        for (; k; k >>= 1) {
            if (k & 1) y *= x;
            x *= x;
        }
        return y;
    }
    mint<MOD> inv() const {
        assert (value != 0);
        int64_t a = value, b = MOD;
        int64_t x = 0, y = 1;
        for (int64_t u = 1, v = 0; a; ) {
            int64_t q = b / a;
            x -= q * u; std::swap(x, u);
            y -= q * v; std::swap(y, v);
            b -= q * a; std::swap(b, a);
        }
        assert (value * x + MOD * y == b);
        assert (b == 1);
        return x;
    }
    inline mint<MOD> operator /  (mint<MOD> other) const { return *this *  other.inv(); }
    inline mint<MOD> operator /= (mint<MOD> other)       { return *this *= other.inv(); }
    inline bool operator == (mint<MOD> other) const { return value == other.value; }
    inline bool operator != (mint<MOD> other) const { return value != other.value; }
};
template <int32_t MOD> mint<MOD> operator * (int64_t value, mint<MOD> n) { return mint<MOD>(value) * n; }
template <int32_t MOD> std::ostream & operator << (std::ostream & out, mint<MOD> n) { return out << n.value; }


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 H, size_t W>
matrix<T, H, W> operator + (matrix<T, H, W> const & a, matrix<T, H, W> const & b) {
    matrix<T, H, W> c;
    REP (y, H) REP (x, W) c[y][x] = a[y][x] + b[y][x];
    return c;
}

template <typename T, size_t N>
array<T, N> operator + (array<T, N> const & a, array<T, N> const & b) {
    array<T, N> c;
    REP (i, N) c[i] = a[i] + b[i];
    return c;
}

template <typename T, size_t H, size_t W>
matrix<T, H, W> zero_matrix() {
    return {};
}

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) << endl;
    }
    return 0;
}
0