結果
問題 | No.42 貯金箱の溜息 |
ユーザー |
![]() |
提出日時 | 2020-06-18 02:11:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,286 ms / 5,000 ms |
コード長 | 3,504 bytes |
コンパイル時間 | 993 ms |
コンパイル使用メモリ | 94,060 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-03 12:37:46 |
合計ジャッジ時間 | 5,783 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 |
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <vector>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;const ll MOD = 1000000009;template <typename T>struct matrix{int n, m;vector<vector<T>> dat;matrix(int n_, int m_){n = n_; m = m_;for(int i = 0; i < n; i++){dat.push_back(vector<T>(m));}}};template <typename T>bool prod(matrix<T> a, matrix<T> b, matrix<T> &ans){if(a.m != b.n) return false;for(int i = 0; i < a.n; i++){for(int j = 0; j < b.m; j++){ans.dat[i][j] = 0;for(int k = 0; k < b.n; k++){ans.dat[i][j] += (a.dat[i][k]*b.dat[k][j])%MOD;ans.dat[i][j] %= MOD;}}}return true;}template <typename T>void copy_mat(matrix<T> a, matrix<T> &b){for(int i = 0; i < a.n; i++){for(int j = 0; j < a.m; j++){b.dat[i][j] = a.dat[i][j];}}}template <typename T>void pow(matrix<T> a, ll n, matrix<T> &ans){matrix<T> buf(a.n, a.n);matrix<T> tmp(a.n, a.n);copy_mat(a, tmp);for(int i = 0; i < a.n; i++) {for(int j = 0; j < a.n; j++){ans.dat[i][j] = 0;}ans.dat[i][i] = 1;}for(int i = 0; i <= 60; i++){ll m = (ll)1 << i;if(m&n){prod(tmp, ans, buf);copy_mat(buf, ans);}prod(tmp, tmp, buf);copy_mat(buf, tmp);}}template <typename T>void print_mat(matrix<T> a){for(int i = 0; i < a.n; i++){for(int j = 0; j < a.m; j++){cout << a.dat[i][j] << ' ';}cout << endl;}}ll dp[6][505];int coin[6] = {1, 5, 10, 50, 100, 500};matrix<ll> mat(6, 6);ll calc(int l, int r){for(int i = 0; i <= 500; i++){for(int j = 0; j < 6; j++){dp[j][i] = 0;}}dp[l][0] = 1;for(int i = 0; i < 500; i++){for(int j = l; j <= r; j++){for(int k = j; k <= r; k++){if(i+coin[k] <= 500){dp[k][i+coin[k]] += dp[j][i];dp[k][i+coin[k]] %= MOD;}}}}return dp[r][500];}void init(){for(int i = 0; i < 6; i++){for(int j = 0; j < 6; j++){mat.dat[i][j] = calc(i, j);}}for(int i = 0; i <= 500; i++){for(int j = 0; j < 6; j++){dp[j][i] = 0;}}dp[0][0] = 1;for(int i = 0; i < 500; i++){for(int j = 0; j < 6; j++){for(int k = j; k < 6; k++){if(i+coin[k] <= 500){dp[k][i+coin[k]] += dp[j][i];dp[k][i+coin[k]] %= MOD;}}}}}void solve(){ll m;cin >> m;int rem = m%500;ll n = m/500;matrix<ll> vec(1, 6), ans(1, 6);for(int i = 0; i < 6; i++) vec.dat[0][i] = dp[i][rem];matrix<ll> buf(6, 6);pow<ll>(mat, n, buf);// print_mat(buf);// print_mat(vec);prod(vec, buf, ans);ll ret = 0;for(int i = 0; i < 6; i++){ret += ans.dat[0][i];ret %= MOD;}cout << ret << endl;}int main(){ios::sync_with_stdio(false);cin.tie(0);cout << setprecision(10) << fixed;init();// print_mat(mat);int t;cin >> t;for(int i = 0; i < t; i++){solve();}}