Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int MOD = 1e9+7;
- ll f[16][135];
- ll pw10[16];
- void init(){
- pw10[0] = 1;
- for (int i = 1; i <= 15; i++) pw10[i] = pw10[i - 1] * 10;
- for (int dig = 0; dig <= 9; dig++) f[0][dig] = dig;
- for (ll pos = 1; pos <= 15; pos++)
- for (int dig = 0; dig <= 9; dig++){
- f[pos][dig] = dig * pw10[pos] % MOD;
- for (int d2 = 0; d2 <= 9; d2++)
- f[pos][dig] += f[pos - 1][d2];
- f[pos][dig] %= MOD;
- cerr << pos << '/' << dig << ' ' << f[pos][dig] << '\n';
- }
- }
- int digit[16];
- void buildArray(ll num){
- for (int i = 0; i <= 15; i++)
- digit[i] = num % 10,
- num /= 10;
- }
- ll n;
- ll calculate(){
- ll answer = 0;
- for (int pos = 15; pos >= 0; pos--)
- for (int dig = 0; dig <= 9; dig++)
- if (dig < digit[pos])
- answer += f[pos][dig], answer %= MOD;
- else {
- n -= dig * pw10[pos];
- answer += dig * (n + 1) % MOD;
- cerr << pos << ' ' << answer << '\n';
- break;
- }
- return answer;
- }
- main(){
- init();
- cin >> n; buildArray(n);
- cout << calculate();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement