Advertisement
zipdang04

QHDCS

Dec 25th, 2021
1,332
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. const int MOD = 1e9+7;
  6.  
  7. ll f[16][135];
  8. ll pw10[16];
  9. void init(){
  10.     pw10[0] = 1;
  11.     for (int i = 1; i <= 15; i++) pw10[i] = pw10[i - 1] * 10;
  12.  
  13.     for (int dig = 0; dig <= 9; dig++) f[0][dig] = dig;
  14.     for (ll pos = 1; pos <= 15; pos++)
  15.         for (int dig = 0; dig <= 9; dig++){
  16.             f[pos][dig] = dig * pw10[pos] % MOD;
  17.             for (int d2 = 0; d2 <= 9; d2++)
  18.                 f[pos][dig] += f[pos - 1][d2];
  19.             f[pos][dig] %= MOD;
  20.             cerr << pos << '/' << dig << ' ' << f[pos][dig] << '\n';
  21.         }
  22. }
  23.  
  24. int digit[16];
  25. void buildArray(ll num){
  26.     for (int i = 0; i <= 15; i++)
  27.         digit[i] = num % 10,
  28.         num /= 10;
  29. }
  30.  
  31. ll n;
  32. ll calculate(){
  33.     ll answer = 0;
  34.     for (int pos = 15; pos >= 0; pos--)
  35.         for (int dig = 0; dig <= 9; dig++)
  36.             if (dig < digit[pos])
  37.                 answer += f[pos][dig], answer %= MOD;
  38.             else {
  39.                 n -= dig * pw10[pos];
  40.                 answer += dig * (n + 1) % MOD;
  41.                 cerr << pos << ' ' << answer << '\n';
  42.                 break;
  43.             }
  44.     return answer;
  45. }
  46.  
  47. main(){
  48.     init();
  49.     cin >> n; buildArray(n);
  50.     cout << calculate();
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement