結果
問題 | No.41 貯金箱の溜息(EASY) |
ユーザー |
|
提出日時 | 2024-01-01 21:11:11 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 23 ms / 5,000 ms |
コード長 | 792 bytes |
コンパイル時間 | 5,682 ms |
コンパイル使用メモリ | 309,008 KB |
実行使用メモリ | 6,816 KB |
最終ジャッジ日時 | 2024-09-27 17:30:05 |
合計ジャッジ時間 | 6,264 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 2 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;#define rep(i,m,n,k) for (int i = (int)(m); i < (int)(n); i += (int)(k))#define rrep(i,m,n,k) for (int i = (int)(m); i > (int)(n); i += (int)(k))#define ll long long#define list(T,A,N) vector<T> A(N);for(int i=0;i<(int)(N);i++){cin >> A[i];}constexpr ll M = 100001;using mint = static_modint<1000000009>;int main(){vector<mint> S(M+1,mint(0));S[0] = 1;rep(d,1,10,1){rep(i,0,M+1-d,1){S[i+d] += S[i];}};rep(i,0,M,1){S[i+1] += S[i];}ll T;cin >> T;ll m;mint ans;rep(_,0,T,1){cin >> m;m /= 111111;ans = S[m];cout << ans.val() << endl;}return 0;}