fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define endl     '\n'
  5. #define int      long long
  6.  
  7. const int N = 2e5, oo = 2e18, MOD = 1e9+7;
  8.  
  9.  
  10. int po[20];
  11.  
  12. int x;
  13. string s; 
  14. int n;
  15. pair<int, int> dp[20][163][2];
  16. bool vis[20][163][2];
  17. pair<int, int> ans(int i, int sum, bool tight) {
  18.     if (i >= n) {
  19.         return {sum == x, 0};
  20.     }
  21.     auto& ret = dp[i][sum][tight];
  22.     if (vis[i][sum][tight]) {
  23.         return ret;
  24.     }
  25.     vis[i][sum][tight] = 1;
  26.     ret = {0, 0};
  27.     int en = (tight ? 9 : s[i] - '0');
  28.     for (int d = 0; d <= en; d++) {
  29.         auto cur = ans(i + 1, sum + d, ((tight || d < en)));
  30.         ret.first += cur.first;
  31.         ret.second = (cur.second + ret.second) % MOD;
  32.         int pos = n - i - 1;
  33.         int contrib = d * po[pos] % MOD;
  34.         int add = contrib * cur.first % MOD;
  35.         ret.second = (ret.second + add) % MOD;
  36.     }
  37.     return ret;
  38. }
  39. pair<int, int> count(int x) {
  40.     s = to_string(x);
  41.     n =  s.size();
  42.     memset(vis, 0, sizeof vis);
  43.     return ans(0, 0, 0);
  44. }
  45. void solve() {
  46.     int k;
  47.     cin >> x >> k;
  48.     n = s.size();
  49.     int ans = -1;
  50.     int l = 1, r = 1e18;
  51.     while (l <= r) {
  52.         int mid = (l + r) / 2;
  53.         auto cur = count(mid);
  54.         if (cur.first >= k) {
  55.             ans = cur.second;
  56.             r = mid - 1;
  57.         } else {
  58.             l = mid + 1;
  59.         }
  60.     }
  61.     cout << ans << endl;
  62. }
  63.  
  64.  
  65. signed main() {
  66.     ios_base::sync_with_stdio(false); 
  67.     cin.tie(NULL); cout.tie(NULL);
  68.     // #ifndef ONLINE_JUDGE 
  69.     //    freopen("input.txt", "r", stdin); 
  70.     //    freopen("output.txt", "w", stdout); 
  71.     // #endif 
  72.     int t; t = 1;
  73.     po[0] = 1;
  74.     for (int i = 1; i < 20; i++) po[i] = (10 * po[i-1]) % MOD;
  75.     cin >> t;
  76.     while (t--) solve();
  77.     return 0;
  78. }
  79.  
Success #stdin #stdout 0.02s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/fn0kGC
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!