Chef vs Bharat Solution | CHEFORA |CODECHEF JULY CHALLENGE

Chef and his friend Bharat have decided to play the game “The Chefora Spell”.

In the game, a positive integer NN (in decimal system) is considered a “Chefora” if the number of digits dd is odd and it satisfies the equationN=∑i=0d−1Ni⋅10i,N=∑i=0d−1Ni⋅10i,

where NiNi is the ii-th digit of NN from the left in 00-based indexing.

Let AiAi denote the ii-th largest Chefora number.

They’ll ask each other QQ questions, where each question contains two integers LL and RR. The opponent then has to answer with(∏i=L+1R(AL)Ai)mod109+7.(∏i=L+1R(AL)Ai)mod109+7.

Bharat has answered all the questions right, and now it is Chef’s turn. But since Chef fears that he could get some questions wrong, you have come to his rescue!

For the work from home Internship Programs : Click here to apply now

Input

The first line contains an integer QQ – the number of questions Bharat asks.
Each of the next QQ lines contains two integers LL and RR.

Output

Print QQ integers – the answers to the questions on separate lines.

Constraints

1≤N,Q≤1051≤N,Q≤105
1≤L<R≤N1≤L<R≤N

Subtasks

Subtask #1 (30 points): 1≤N,Q≤5⋅1031≤N,Q≤5⋅103

Subtask #2 (70 points): Original constraints

Sample Input

2
1 2
9 11

Sample Output

1
541416750

Explanation

For the first question:(A1)A2=12=1.(A1)A2=12=1.
For the second question:(A9)A10⋅(A9)A11=9101⋅9111≡541416750(mod109+7).

SOLUTION

Join telegram channel for updates
Please click 1-2 ads on this website to support us

CPP

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define l1 long long
#define mod 1000000007

l1 power(l1 bs, l1 pw){
    l1 res=1;
    while(pw!=0){
        if(pw%2==0){
            bs=((bs%mod)*(bs%mod))%mod;
            pw=floor(pw/2);
        }
        else{
            res=((res%mod)*(bs%mod))%mod;
            pw=pw-1;
        }
    }
    return res;
}

l1 chefona(l1 num){
    l1 chefnum=num;
    l1 retnum=0;
    if(num<10){
        retnum=chefnum;
    }
    else if(num>=10){
        num=num/10;
        while(num!=0){
            chefnum=chefnum*10+num%10;
            num=num/10;
        }
        retnum=chefnum;
    }
    return retnum;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    l1 a[100001]={0};
    l1 prearray[100001]={0};
    for(l1 i=1;i<=100001;i++){
        a[i]=chefona(i);
        prearray[i]=prearray[i-1]+a[i];
    }
    l1 t;
    cin>>t;
    while(t--){
        l1 l,r;
        cin>>l>>r;
        l1 diff=prearray[r]-prearray[l];
        cout<<power(a[l],diff)<<"\n";
        
    }
    return 0;
}



Python

def findpower(base,power):
    mod = 10**9+7
    res = 1
    while power!=0:
        if power%2==0:
            base = ((base%mod)*(base%mod))%mod
            power = power//2
        else:
            res = ((res%mod)*(base%mod))%mod
            power = power-1
    return res


def findshefola(num):
    palin = num
    num = num//10
    while num>0:
        palin = palin*10+num%10
        num = num//10
    return palin


arr = [0]*(10**5+1)
arrsm = [0]*(10**5+1)
for i in range(1,10**5+1):
    arr[i] = findshefola(i)
    arrsm[i] = arrsm[i-1] + arr[i]

for _ in range(int(input())):
    l,r = map(int,input().split())
    power = arrsm[r]-arrsm[l]
    print(findpower(arr[l],power))

Join Telegram Channel

Read More Post Here