結果
問題 | No.42 貯金箱の溜息 |
ユーザー |
|
提出日時 | 2017-11-01 21:59:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 79 ms / 5,000 ms |
コード長 | 1,077 bytes |
コンパイル時間 | 2,240 ms |
コンパイル使用メモリ | 194,308 KB |
最終ジャッジ日時 | 2025-01-05 03:41:42 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int MOD = int(1e9) + 9;const int COIN[] = { 1, 5, 10, 50, 100, 500 };int dp[3000];int inv_mod(int v, int mod = MOD) {int res = 1;for (int i = mod - 2; i; i >>= 1) {if (i & 1) res = 1LL * res * v % mod;v = 1LL * v * v % mod;}return res;}long long solve(long long m) {long long res = 0;long long q = m / 500, r = m % 500;for (int i = 0; i < 6; ++i) {long long coe = 1;for (int j = 0; j < 6; ++j) {if (i == j) continue;coe = coe * (MOD - (q - j) % MOD) % MOD;}for (int j = 0; j < 6; ++j) {if (i == j) continue;coe = coe * (MOD - inv_mod(i - j) % MOD) % MOD;}(res += coe * dp[i * 500 + r] % MOD) %= MOD;}return res;}signed main() {ios::sync_with_stdio(false);dp[0] = 1;for (int i = 0; i < 6; ++i) {for (int j = 0; j + COIN[i] < 3000; ++j) {(dp[j + COIN[i]] += dp[j]) %= MOD;}}int T;cin >> T;while (T--) {long long M;cin >> M;cout << solve(M) << endl;}return 0;}