結果
問題 | No.2455 Numbers Dictionary |
ユーザー |
|
提出日時 | 2023-09-01 23:39:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 147 ms / 2,000 ms |
コード長 | 1,533 bytes |
コンパイル時間 | 1,668 ms |
コンパイル使用メモリ | 163,308 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2025-01-03 12:50:26 |
合計ジャッジ時間 | 4,921 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template<typename T> T ADD(T a, T b){ T res; return __builtin_add_overflow(a, b, &res)? std::numeric_limits<T>::max() : res; } template<typename T> T MUL(T a, T b){ T res; return __builtin_mul_overflow(a, b, &res)? std::numeric_limits<T>::max() : res; } void solve(){ ll n, k; cin >> n >> k; //n以下かつkより辞書順で小さい string t = to_string(k); auto f = [&](ll v, ll k){ string s = to_string(v); ll dp[s.size() + 1][2][2] = {}; for(int i = 1; i + '0' <= min(s[0], t[0]); i++) dp[1][i + '0' == s[0]][i + '0' == t[0]]++; for(int i = 1; i < s.size(); i++){ for(int j = 0; j < 2; j++){ int r = j ? s[i] - '0' : 9; for(int k = 0; k < 2; k++){ r = min(r, k ? (i >= t.size() ? -1 : t[i] - '0') : 9); for(int l = 0; l <= r; l++){ dp[i + 1][j & (l == s[i] - '0')][k & (l == t[i] - '0')] += dp[i][j][k]; } } } } return dp[s.size()][0][0] + dp[s.size()][1][0] + dp[s.size()][0][1] + dp[s.size()][1][1]; }; ll d = 9, ans = 0; while(d < n){ ans += f(d, k); d = ADD(MUL(d, 10ll), 9ll); } ans += f(n, k); cout << ans << '\n'; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while(T--){ solve(); } }