Goku's Power

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 $Nlog_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 $rep[n]$ represent the number $n$ repeating $n$ times.

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

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

(This is not addition, it's concatenation)

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

First let's calculate $rep[n]$.

To find pattern, first observe any single digit number, let's say $5$:

$55555 = 5 \cdot 10^4 + 5 \cdot 10^3 + 5 \cdot 10^2 + 5 \cdot 10^1 + 5 \cdot 10^0$

Now observe for multiple digits, let's say $12$:

$12...12 = 12 \cdot 10^{11 \cdot 2} + 12 \cdot 10^{10 \cdot 2}  + ..... + 12 \cdot 10^{1 \cdot 2} + 12 \cdot 10^{0 \cdot 2}$

Generalization for multiple digits:

$n...n = n \cdot 10^{(n-1) \cdot d} + n \cdot 10^{(n-2) \cdot d}  + ..... + n \cdot 10^{1 \cdot d} + n \cdot 10^{0 \cdot d}$

Take $n$ common, remaining part is in geometric progression with initial value as $1$ and ratio as $10^d$ and there are n terms.

By using sum of GP formula which is:

$a + ar + ar^2 + ... + ar^{n-1} = \frac {a \cdot (r^n-1)} {r-1}$

We can compute $rep[n]$ as follows:

$rep[n] = \frac {n \cdot (10^{d \cdot n} - 1)} {(10^d - 1)}$

(Use Modular Inverse)

Let $srep[i]$ represent size of $rep[i]$.

It's obvious that $srep[i] = i \cdot d$

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

Now, let's evaluate the answer by concatention:

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

(This is not addition, it's concatenation)

First let's concatenate second part to first part:

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

$value[n] = rep[n] * 10^{size[n-1]} + value[n-1]$

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

We need to append $srep[n]$ zeroes and add n to it.

$value[n] = value[n] * 10^{srep[n]} + rep[n]$

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

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 modular_inverse(ll a,ll mod2=mod)
{
    // By Fermat's little theorem
    return binexp(a,mod2-2,mod2);
}

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]=i*d+sz[i-1]+i*d;
        ll val=((i*(binexp(10,d*i)-1))%mod * modular_inverse(binexp(10,d) - 1))%mod;
        ans[i]=(((((val*binexp(10,sz[i-1]))%mod + ans[i-1])%mod)*binexp(10,i*d))%mod + val)%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 : Naveen

// Program Start
// Libraries and Namespace Start
#include <bits/stdc++.h>
using namespace std;
// Libraries and Namespace End

//----------------------------------------------------------------

// Important Shortcuts Start
// Macros Start
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(), v.end()
// Macros End

// Declarations Start
typedef long long int ll;
typedef vector<ll> vll;
// Declarations End

// Constants Start
const ll mod1 = 1e9 + 7;
const char newl = '\n';
// Constants End

// Binary Exponentiation Start
ll power(ll b, ll p, const ll mod) {
    if (b <= 0 || p < 0) {
        throw invalid_argument("The numbers can't be negative.");
    }
    ll res = 1;
    b %= mod;
    while (p > 0) {
        if (p & 1) {
            res = res * b % mod;
        }
        b = b * b % mod;
        p >>= 1;
    }
    return res;
}
// Binary Exponentiation End

// Modular Arithmetic Start
// Modular Inverse Function Start
inline ll mod_inv(ll n, const ll mod = mod1) {
    if (n < 0) {
        throw invalid_argument("The number can't be negative.");
    }
    return power(n, mod - 2, mod);
}
// Modular Inverse Function End
// Modular Arithmetic End


//----------------------------------------------------------------

// Solution Class Start
class Solution {
public:
    vll ans;

    Solution() {
        ans.assign(1e5 + 1, 0);
        ans[1] = 1;
        ll cou = 1;
        ll d = 1;
        for (ll i = 2;i <= ans.size();i++) {
            switch (i) {
                case 10:
                case 100:
                case 1000:
                case 10000:
                case 100000:
                    d++;
            }
            ll p = power(10, i * d, mod1);
            ans[i] = (ans[i - 1] * p) % mod1;
            cou += i * d;
            p = power(10, i * d, mod1);
            ll val = ((((p + mod1 - 1) % mod1) * (mod_inv((power(10, d, mod1) + mod1 - 1) % mod1, mod1))) % mod1 * i) % mod1;
            ans[i] = ((val * power(10, cou, mod1)) % mod1 + (ans[i] + val) % mod1) % mod1;
            cou += i * d;
        }
    }

    void solve(ll index) {
        //----------------------------------------------------------------

        ll n, i, j, k;
        cin >> n;
        cout << ans[n] << newl;

        // cout << "Case #" << index << ": " << ans << newl;

        //----------------------------------------------------------------
    }

    bool test_cases = true;
};
// Solution Class End

// Main Function Start
int main() {
    Solution sol;
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll test_cases = 1;
    if (sol.test_cases) {
        cin >> test_cases;
    }
    for (ll test_case = 1; test_case <= test_cases; ++test_case) {
        sol.solve(test_case);
    }
    return 0;
}
// Main Function End
// Program End
//----------------------------------------------------------------