結果
問題 | No.2302 Carry X Times |
ユーザー | 👑 Nachia |
提出日時 | 2023-05-12 21:54:00 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 55 ms / 2,000 ms |
コード長 | 1,767 bytes |
コンパイル時間 | 1,377 ms |
コンパイル使用メモリ | 96,084 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-28 18:03:45 |
合計ジャッジ時間 | 2,752 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 24 |
ソースコード
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <map> #include <tuple> #include <atcoder/modint> using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; i64 N; map<tuple<bool, bool, i64, bool, int>, Modint> mem; Modint dp(bool boundedA, bool boundedB, i64 dig, bool do_inc, int inccnt){ if(inccnt < 0) return 0; if(dig == 0){ if(do_inc) return 0; if(inccnt > 0) return 0; return 1; } if(mem.count({ boundedA, boundedB, dig, do_inc, inccnt })) return mem[{ boundedA, boundedB, dig, do_inc, inccnt }]; Modint ans = 0; int digN = N / dig % 10; i64 nxdig = dig / 10; rep(da, 10) rep(db, 10){ if(da > digN && !boundedA) continue; if(db > digN && !boundedB) continue; bool nxboundedA = da < digN || boundedA; bool nxboundedB = db < digN || boundedB; rep(inc, 2){ bool real_do_inc = inc + da + db >= 10; if(real_do_inc && !do_inc) continue; if(!real_do_inc && do_inc) continue; ans += dp(nxboundedA, nxboundedB, nxdig, inc, inccnt - inc); } } return mem[{ boundedA, boundedB, dig, do_inc, inccnt }] = ans; } int main(){ int T; cin >> T; rep(t,T){ mem.clear(); cin >> N; int X; cin >> X; cout << dp(false, false, 1'000'000'000'000'000'000, false, X).val() << endl; } return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;