Dare to Solve

Author : shailesh_2004

Required Knowledge : Geometric Progression, Precomputation, Binary Search, Modular Arithmetic, Heavy Implementation

Time Complexity : $O(k \cdot log(10^9+7) + q\cdot logk)$

Editorialist : shailesh_2004

Approach:

The main difficulty of the problem is that both the array size and the numeric string size can be extremely large (up to $10^{14}$ ), so constructing them explicitly is impossible.

Hence, we must work with a compressed representation using blocks.

Block Representation

Each pair $(c[i], l[i])$ represents a block where:

value $c[i]$ is repeated $l[i]$ times in the array let $d[i] = digits(c[i])$

We maintain the following:

Array indices

$L[i] =$ starting index of block $i$ in array
$R[i] =$ ending index

Digit indices (in the big string)

$prel[i] =$ starting digit position
$prer[i] =$ ending digit position

Prefix values $(prod[i])$

Let $prod[i]$ denote the numeric value formed by concatenating all blocks from $0$ to $i$ .

We compute:

 $prod[i] = prod[i-1] \cdot 10^{d[i] \cdot l[i]} + rep(c[i], d[i], l[i])$

rep() Function

The function $rep(n, d, f)$ computes the number formed by repeating $n$ exactly $f$ times.

Example: $n=12, f=3$ becomes $121212$

We observe:

 $121212 = 12 \cdot (10^4 + 10^2 + 1)$

In general:

 $rep(n, d, f) = n \cdot (1 + 10^d + 10^{2\cdot d} + 10^{3\cdot d} + \dots + 10^{(f-1)\cdot d})$

This is a geometric progression:

 $= n \cdot \frac{10^{d\cdot f} - 1}{10^d - 1}$

We compute this using modular inverse:

ll rep(ll n,ll d,ll f)
{
    ll num=(binexp(10,d*f)-1+mod)%mod;
    ll den=(binexp(10,d)-1+mod)%mod;
    return (n*((num*modular_inverse(den))%mod)%mod);
}

Type E Query:

We are given array indices $x, y$ , we convert them to digit indices: If $x$ lies in block $i$ , then $x$ becomes $prel[i] + (x-L[i])\cdot d[i]$

Similarly for $y$ : $y$ becomes $prel[i] + (y-L[i])\cdot d[i] + d[i] - 1$

Now, the problem reduces to a Type D Query

Type D Query:

We need substring from digit $x$ to $y$ .

By using binary search, find the blocks containing $x$ and $y$ as $lind$ and $rind$ respectively.

Case-1: Same block

Directly compute using $getpart()$ function given in Setter's code.

Case-2: Different blocks

Split into $3$ parts as below:

Left part: $x$ → $prer[lind]$
Middle part: full blocks $[lind+1 \dots rind-1]$

 $mid=prod[rind−1]−prod[lind]⋅10^{(prer[rind−1]−prer[lind])}$

Right part: prel[rind] → y

Combine all parts:

If no middle:

 $ans = left \cdot 10^{len(right)} + right$

Otherwise:

 $ans = left \cdot 10^{len(mid+right)} + mid \cdot 10^{len(right)} + right$

Note that all these computations are performed with modulo $10^9+7$ .

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 endl "\n"
#define mod 1000000007
#define tot(a) a.begin(),a.end()
 
// ------------------------------------------------------------------------------------

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 rep(ll n,ll d,ll f)
{
    ll num=(binexp(10,d*f)-1+mod)%mod;
    ll den=(binexp(10,d)-1+mod)%mod;
    return (n*((num*modular_inverse(den))%mod)%mod);
}

// reusable block
ll getPart(ll c,ll d,ll prel,ll x,ll y)
{
    ll st=prel-1;

    ll ind1=(x-st+d-1)/d, ind2=(y-st+d-1)/d;
    ll pos1=(x-st)%d; if(!pos1) pos1=d;
    ll pos2=(y-st)%d; if(!pos2) pos2=d;

    vector<ll> dig(d+1);
    ll t=c;
    for(ll i=d;i>=1;i--) dig[i]=t%10, t/=10;

    if(ind1==ind2)
    {
        ll ans=0;
        for(ll i=pos1;i<=pos2;i++) ans=ans*10+dig[i];
        return ans;
    }

    ll ans=(ind2-ind1-1>=1 ? rep(c,d,ind2-ind1-1):0);
    ans=ans*binexp(10,pos2)%mod;

    ll val=0;
    for(ll i=1;i<=pos2;i++) val=(val*10+dig[i])%mod;
    ans=(ans+val)%mod;

    val=0;
    for(ll i=pos1;i<=d;i++) val=(val*10+dig[i])%mod;
    return (val*binexp(10,(d*(ind2-ind1-1)+pos2))%mod + ans)%mod;
}

void solve()
{
    ll k;
    cin>>k;
    vector<ll> c(k),l(k),d(k),prel(k),prer(k),prod(k),L(k),R(k);

    ll prev=0,prevind=0,prevprod=0;
    for(ll i=0;i<k;i++)
    {
        cin>>c[i]>>l[i];

        ll x=c[i]; d[i]=0;
        while(x) d[i]++, x/=10;

        L[i]=prevind+1;
        R[i]=prevind+l[i];
        prevind=R[i];

        prel[i]=prev+1;
        prer[i]=prev+d[i]*l[i];
        prev=prer[i];

        ll val=(c[i]*( (binexp(10,d[i]*l[i])-1+mod)%mod )%mod
               *modular_inverse((binexp(10,d[i])-1+mod)%mod))%mod;

        prod[i]=(prevprod*binexp(10,d[i]*l[i])%mod + val)%mod;
        prevprod=prod[i];
    }

    auto idx=[&](vector<ll>& a,ll x)
    {
        ll l=0,r=k-1,ans=0;
        while(l<=r)
        {
            ll m=(l+r)/2;
            if(a[m]<=x) ans=m,l=m+1;
            else r=m-1;
        }
        return ans;
    };

    ll q; cin>>q;
    while(q--)
    {
        char type; ll x,y;
        cin>>type>>x>>y;

        if(type=='E')
        {
            ll xi=idx(L,x), yi=idx(L,y);
            x=prel[xi]+(x-L[xi])*d[xi];
            y=prel[yi]+(y-L[yi])*d[yi]+d[yi]-1;
        }

        ll lind=idx(prel,x), rind=idx(prel,y);

        if(lind==rind)
        {
            cout<<getPart(c[lind],d[lind],prel[lind],x,y)<<"\n";
            continue;
        }

        ll mid = (rind-lind-1>=1) ?
            (prod[rind-1] - prod[lind]*binexp(10,prer[rind-1]-prer[lind])%mod + mod)%mod : 0;

        ll left = getPart(c[lind],d[lind],prel[lind],x,prer[lind]);
        ll right = getPart(c[rind],d[rind],prel[rind],prel[rind],y);

        ll ans;
        if(rind-1==lind)
        {
            ans=(left*binexp(10,y-prer[lind])%mod + right)%mod;
        }
        else
        {
            ans=(mid*binexp(10,y-(prel[rind]-1))%mod + right)%mod;
            ans=(left*binexp(10,y-prer[lind])%mod + ans)%mod;
        }
        cout<<ans<<"\n";
    }
}

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

Tester's Code:

//Author: nagajahnavidann1 >_<
//code well!
#include <bits/stdc++.h>
using namespace std;
 
 
#define fastio ios::sync_with_stdio(false); cin.tie(nullptr)
#define pb push_back
#define Yes cout << "Yes\n"
#define No cout << "No\n"
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define fe first
#define se second
#define full(v) v.begin() ,v.end()
typedef bool bl;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> prll;
typedef tuple<ll, ll, ll> tupll;
typedef stack<ll> stll;
typedef queue<ll> qll;
typedef vector<bl> vbl;
typedef vector<ll> vll;
typedef vector<str> vstr;
typedef vector<vll> vvll;
typedef set<ll> setll;
typedef multiset<ll> mltsetll;
typedef map<int, int> mpii;
typedef map<ll, ll> mpll;
typedef multimap<ll, ll> mltmpll;
 
template<class T>void inp(vector<T>&a){for(auto &x:a)cin>>x;}
template<class T> void look(vector<T>&a){for(auto &x:a)cout<<x<<' ';cout<<endl;}
template<class T> void look(set<T>&a){for(auto &x:a)cout<<x<<' ';cout<<endl;}
template<class T> void look(map<T,T>&a){for(auto &x:a)cout<<x.ff<<' '<<x.ss<<endl;cout<<endl;}
 
//------------------declarations-------------
const ll MOD=1e9+7;
const ll INF=1e18;
 
//------------------------fns-----------------
ll power(ll a, ll b){ll ans = 1;while(b){if(b & 1ll)ans = (ans*a)%MOD;a = (a*a)%MOD;b >>= 1ll;}return ans%MOD;}
bool is_prime(int n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(int i=5;i*i<=n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;}
 
//---------------------timer-----------------
const auto start_time = std::chrono::high_resolution_clock::now();
// void time_taken(){auto end_time = std::chrono::high_resolution_clock::now();std::chrono::duration<double> diff = end_time-start_time;cerr<<"Time Taken : "<<diff.count()<<"\n";}
 
//---------------------solve------------------
vector<ll>a,nod,noe,cs;
ll k;
ll fun(ll n,int mode){
    auto it=lower_bound(full(noe),n);
    ll idx=it-noe.begin();
    ll pre=(idx==0)?0:noe[idx-1];
    ll pd=(idx==0)?0:nod[idx-1];
    ll rem=n-pre-1;
    if(mode){
        rem++;
        return pd+rem*((ll)log10(a[idx])+1);}
    return pd+rem*((ll)log10(a[idx])+1)+1;
}
ll eval(ll n)
{
    if(n<=0)return 0;
    auto it=lower_bound(full(nod),n);
    ll idx=it-nod.begin();
    if(nod[idx]==n)return cs[idx];
    ll pv=(idx==0)?0:cs[idx-1];
    ll pd=(idx==0)?0:nod[idx-1];
    n-=pd;
    //now there are n digits of ind to be considered
    ll dig=log10(a[idx])+1;
    ll part=n/dig;
    ll rem=n%dig;
    ll v1=(power(10,dig*part%(MOD-1))-1+MOD)%MOD* power(power(10,dig)-1+MOD,MOD-2)%MOD; // power(10,full*dig-n)%MOD;
    v1=(a[idx]*v1%MOD*power(10,rem)%MOD+a[idx]/(ll)round(pow(10,dig-rem))%MOD)%MOD;
    pv= (pv*power(10,n%(MOD-1))%MOD+v1%MOD)%MOD;
    return pv;
 
}
void dj()
{ 
    ll val;
    cin>>k;
    a.resize(k);//numbers
    nod.resize(k);//no of digis
    noe.resize(k);//no of eles
    cs.resize(k);//current number after i th number
    ll cnod=0,cnoe=0,ccs=0;
    for(int i=0;i<k;i++)
    {
        ll t;
        cin>>a[i]>>t;
        ll dig=(ll)log10(a[i])+1;
        // cout<<power(10,dig*t%(MOD-1))*ccs<<"-"<<a[i]*(power(10,dig*t%(MOD-1))-1+MOD)%MOD*power(power(10,dig)-1,MOD-2)%MOD<<" ";
        ccs= (power(10,dig*t%(MOD-1))*ccs%MOD+a[i]*(power(10,dig*t%(MOD-1))-1+MOD)%MOD*power(power(10,dig)-1,MOD-2)%MOD)%MOD;
        cs[i]=ccs;
        cnoe=cnoe+t;
        cnod=cnod+t*dig;//keep raw values!! not mods!!
        noe[i]=cnoe;
        nod[i]=cnod;
        
    }
    ll q;
    cin>>q;
    while(q--)
    {
        char ch;
        ll l,r;
        cin>>ch>>l>>r;
        if(ch=='E'){
        l=fun(l,0);
        r=fun(r,1);
        }
        //now all are into digit numbers...
        l--;
        // cout<<r<<" ";
        // cout<<eval(r)<<"fv ";
        cout<<(eval(r)-eval(l)*power(10, (r-l)%(MOD-1))%MOD+MOD)%MOD<<endl;
 
    }
 
}
 
// ------------------------------------------------------------------------------------
 
signed main(){
	fastio;
	// int t;cin>>t;while(t--)
	dj();
	// time_taken();
}

Editorial for Problem A