結果
問題 | No.41 貯金箱の溜息(EASY) |
ユーザー |
|
提出日時 | 2024-09-30 16:17:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 5,000 ms |
コード長 | 2,310 bytes |
コンパイル時間 | 5,963 ms |
コンパイル使用メモリ | 287,036 KB |
最終ジャッジ日時 | 2025-02-24 14:17:20 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 2 |
ソースコード
// #pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;using mint = modint998244353;// using mint = modint1000000007;using ll = long long;using ull = unsigned long long;using ld = long double;using pii = pair<int, int>;using pll = pair<ll, ll>;using T = tuple<int, int, int>;using G = vector<vector<int>>;#define rep(i, n) for (ll i = 0; i < (n); ++i)#define rep2(i, a, b) for (ll i = a; i < (b); ++i)#define rrep2(i, a, b) for (ll i = a-1; i >= (b); --i)#define rep3(i, a, b, c) for (ll i = a; i < (b); i+=c)#define rng(a) a.begin(),a.end()#define rrng(a) a.rbegin(),a.rend()#define popcount __builtin_popcount#define popcountll __builtin_popcountll#define fi first#define se second#define UNIQUE(v) sort(rng(v)), v.erase(unique(rng(v)), v.end())#define MIN(v) *min_element(rng(v))#define MAX(v) *max_element(rng(v))#define SUM(v) accumulate(rng(v),0)#define IN(v, x) (find(rng(v),x) != v.end())template<class T> bool chmin(T &a,T b){if(a>b){a=b;return 1;}else return 0;}template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}template<class T> void printv(vector<T> &v){rep(i,v.size())cout<<v[i]<<" \n"[i==v.size()-1];}template<class T> void printvv(vector<vector<T>> &v){rep(i,v.size())rep(j,v[i].size())cout<<v[i][j]<<" \n"[j==v[i].size()-1];cout<<endl;}const ll dx[] = {0, 1, 0, -1};const ll dy[] = {1, 0, -1, 0};const ll dxx[] = {0, 1, 0, -1, 1, -1, 1, -1};const ll dyy[] = {1, 0, -1, 0, 1, 1, -1, -1};const ll LINF = 1001002003004005006ll;const int INF = 1001001001;const int m = 111111;const ll mod = 1000000009;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t; cin >> t;vector<ll> query(t);rep(i, t) cin >> query[i];ll max_q = MAX(query);ll n = max_q/m;vector<ll> dp(n+1); dp[0] = 1;rep2(j, 1, 10){rep(i, n){if (i+j > n) break;dp[i+j] += dp[i];dp[i+j] %= mod;}}vector<ll> s(n+1); s[0] = 1;rep(i, n) s[i+1] = (s[i]+dp[i+1])%mod;rep(i, t){ll ans = 0;int k = query[i]/m;ans += s[k];ans %= mod;cout << ans << endl;}return 0;}