結果
問題 | No.41 貯金箱の溜息(EASY) |
ユーザー | ttkkggww |
提出日時 | 2022-04-01 23:58:29 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 32 ms / 5,000 ms |
コード長 | 902 bytes |
コンパイル時間 | 4,311 ms |
コンパイル使用メモリ | 259,292 KB |
実行使用メモリ | 7,916 KB |
最終ジャッジ日時 | 2023-08-12 21:45:04 |
合計ジャッジ時間 | 4,970 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge7 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 32 ms
7,844 KB |
testcase_01 | AC | 32 ms
7,916 KB |
コンパイルメッセージ
次のファイルから読み込み: /usr/include/atcoder/modint:1, 次から読み込み: /usr/include/atcoder/convolution.hpp:11, 次から読み込み: /usr/include/atcoder/convolution:1, 次から読み込み: /usr/include/atcoder/all:1, 次から読み込み: main.cpp:3: メンバ関数 ‘atcoder::dynamic_modint<id>::mint& atcoder::dynamic_modint<id>::operator+=(const mint&) [with int id = -1]’ 内, inlined from ‘void init()’ at main.cpp:29:24: /usr/include/atcoder/modint.hpp:192:9: 警告: iteration 99999 invokes undefined behavior [-Waggressive-loop-optimizations] 192 | _v += rhs._v; | ^~ main.cpp: 関数 ‘void init()’ 内: main.cpp:28:24: 備考: within this loop 28 | for(int i = 0;i<100000;i++){ | ~^~~~~~~
ソースコード
#include<bits/stdc++.h> using namespace std; #include<atcoder/all> using namespace atcoder; using ll = long long; using mint = modint; int t; ll x; mint dp[100001][10]; mint dpsum[100000]; void init(){ dp[0][0] = 1; for(int i = 0;i<100000;i++){ for(int j = 0;j<10;j++){ for(int k = max(1,j);k<10;k++){ if(i+k<100001) dp[i+k][k] += dp[i][j]; } } } for(int i = 0;i<100001;i++){ for(int j = 0;j<10;j++){ dpsum[i] += dp[i][j]; } } for(int i = 0;i<100000;i++){ dpsum[i+1] += dpsum[i]; } /* for(int i = 0;i<10;i++){ for(int j = 0;j<10;j++){ cout<<dp[i][j].val()<<' '; } cout<<endl; } for(int i = 0;i<10;i++){ cout<<dpsum[i].val()<<endl; } */ } void solve(){ cout<<dpsum[x/111111].val()<<endl; } signed main(){ cin.tie(nullptr); ios::sync_with_stdio(false); mint::set_mod(1000'000'000+9); init(); cin >> t; while(t--){ cin >> x; solve(); } }