Goku's Experience

Author : shailesh_2004

Required Knowledge : DP, Math, Modulo Arithmetic

Time Complexity : $O(N \cdot log_2N)$

Editorialist : shailesh_2004

Approach:

The value of $n$ depends on the value of $n-1$. The time complexity will be $N \cdot log_2N$ for each $n$ if we calculate the given expression. If we do this for $T$ cases then it will become $T \cdot Nlog_2N$ which gives us TLE. Thus, we should precompute all values from $1$ to $10^5$.

Let's divide the value for $n$ into three parts

$value[n] = n + value[n-1] + n$

(This is not addition, it's concatenation)

To do this concatenation we need number of digits in $value[n-1]$. Let's store each value's size in another array (where $size[i]$ represents number of digits in $value[n]$). Let $d$ be number of digits in the number $n$.

It's obvious that

$size[i] = d + size[i-1] + d$

First let's concatenate second part to first part:

We need to append $size[n-1]$ zeroes to $n$ and add $value[n-1]$. As $size[n-1]$ is large use binary exponentiation and modulo.

Now

$value[n] = n \cdot 10^{size[n-1]} + value[n-1]$

Then let's concatenate third part to current $value[n]$

We need to append $d$ zeroes and add $n$ to it.

Now

$value[n] = value[n] \cdot 10^d + n$

Time complexity is $O(N \cdot log_2N)$, here $log_2N$ factor is because of binary exponentiation.

Setter's Code:

// Author : Shailesh
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define pb push_back
#define mp make_pair
#define endl "\n"
#define mod 1000000007
#define tot(a) a.begin(),a.end()
#define minii *min_element
#define maxii *max_element

ll binexp(ll a,ll b,ll mod2=mod)
{
    ll res=1;
    a%=mod2;
    while(b)
    {
        if(b%2)res=(res*a)%mod2;
        a=(a*a)%mod2;
        b>>=1;
    }
    return res;
}

ll ans[100001];
void precompute()
{
    ans[1]=1;
    ll sz[100001];
    sz[1]=1;
    ll i;
    ll tens[6]={10,100,1000,10000,100000};
    ll j=0;
    ll d=1;
    for(i=2;i<=100000;i++)
    {
        if(i==tens[j])
        {
            j++;
            d++;
        }
        sz[i]=d+sz[i-1]+d;
        ans[i]=(((((i*binexp(10,sz[i-1]))%mod + ans[i-1])%mod)*binexp(10,d))%mod + i)%mod;
    }
}

void solve()
{
    ll n;
    cin>>n;
    cout<<ans[n]<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    precompute();
    ll t;cin>>t;while(t--)
    solve();
    return 0;
}

Tester's Code:

// Author : Adithya
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll              long long
#define vll             vector<ll>
#define pb              push_back
#define NN              1000000
#define mod             1000000007
#define tot(a)          a.begin(),a.end()
#define mini(a)         *min_element(tot(a))
#define maxi(a)         *max_element(tot(a))
#define ppb             pop_back
#define read(a)         for(auto &x : a) cin >> x;
#define print(a)        for(ll i : a) cout << i <<" ";
#define yes             cout << "YES" << endl;
#define no              cout << "NO" << endl;
#define u_m             unordered_map
#define pll             pair<ll, ll>
#define F               first
#define S               second
#define endl            "\n"

vll pre(1e5+1),tenpow(1e6+1),nod(1e5+1);

void solve()
{
    ll n;
    cin>>n;
    cout<<pre[n]<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    ll t=1;cin>>t;

    for(ll i=1;i<=1e5;i++)
    {
        ll c = 0,ii = i;
        while(ii>0)
        {
            c++;
            ii /= 10;
        }
        nod[i] = c;
    }
    
    tenpow[0] = 1;
    for(ll i=1;i<=1e6;i++)
    {
        tenpow[i] = (tenpow[i-1]*10)%mod;
    }

    pre[1] = 1;
    ll cnt = 1;

    for(ll i=2;i<=1e5;i++)
    {
        ll ans = ((pre[i-1]*tenpow[nod[i]])%mod + i)%mod;
        cnt += nod[i];

        ans = (ans + (tenpow[cnt]*i)%mod)%mod;
        cnt += nod[i];

        pre[i] = ans;
    }
    while(t--)
    {
       solve();
    }	
    return 0;
}