結果
問題 | No.41 貯金箱の溜息(EASY) |
ユーザー |
![]() |
提出日時 | 2022-12-20 01:14:19 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 23 ms / 5,000 ms |
コード長 | 722 bytes |
コンパイル時間 | 1,131 ms |
コンパイル使用メモリ | 143,596 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-18 01:41:55 |
合計ジャッジ時間 | 1,702 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 2 |
ソースコード
#include <iostream>#include <vector>#include <cmath>#include <map>#include <set>#include <iomanip>#include <queue>#include <algorithm>#include <numeric>#include <deque>#include <complex>using namespace std;const long long modc = 1e9+9;int main(){long long T, M, q;cin >> T;vector<long long> dp(90001), S(90001);dp[0] = 1;for (int j=1; j<=9; j++){for (int i=0; i<=90000; i++){if (i-j >= 0) dp[i] = (dp[i] + dp[i-j]) % modc;}}S[0] = 1;for (int i=1; i<=90000; i++){S[i] = (S[i-1] + dp[i]) % modc;}for (int i=0; i<T; i++){cin >> M;q = M / 111111;cout << S[q] << endl;}return 0;}