CHEFORA - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Bharat Singla
Tester: Aryan
Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

Precomputation, prefix sums.

PROBLEM

A positive integer N (in decimal system) is considered a “Chefora” if the number of digits d is odd and it satisfies the equation \displaystyle N = \sum_{i=0}^{d-1} N_i \cdot 10^i, where N_i is the i-th digit of N from the left in 0-based indexing.

Let A_i denote the i-th smallest Chefora number.

Answer Q queries, where each query consist of two integer L and R (L < R), and we need to compute \displaystyle \left(\prod_{i = L+1}^R (A_L) ^ {A_i}\right) \bmod{10^9+7}

QUICK EXPLANATION

  • An integer N is considered as chefora number if and only if its decimal representation consists of an odd number of digits, and forms a palindrome.
  • We can generate a list of the smallest 10^5 chefora numbers by iterating on the left half and reversing it to obtain the right half.
  • After building list, prefix sums can be computed to compute \displaystyle P = \sum_{i = L+1}^R A_i, as the answer to query is (A_L) ^P, computed using binary exponentiation

EXPLANATION

Understanding Chefora number

Let us revisit the definition.
If N is a chefora number, we have \displaystyle N = \sum_{i=0}^{d-1} N_i \cdot 10^i, where N_i is the i-th digit of N from the left in 0-based indexing.

Considering N = 23578, we get \displaystyle \sum_{i=0}^{d-1} N_i \cdot 10^i = 2 + 30 + 500 + 7000 + 80000 = 87532. Similarly, for N = 10520, we get \displaystyle \sum_{i=0}^{d-1} N_i \cdot 10^i = 2501

It is easy to notice and prove that \displaystyle\sum_{i=0}^{d-1} N_i \cdot 10^i is nothing but the reverse of decimal representation of N without leading zeros.

Hence, we can see that the decimal representation of N must be a palindrome.

Secondly, we are given that d must be odd, where d is the number of digits.

Hence, a chefora number consists of an odd number of digits, and the decimal representation of N forms a palindrome.

Building list of Chefora numbers

Since all the queries have L \lt R \leq 10^5, we only need the first 10^5 chefora numbers in sorted order.

First few numbers of this list are 1,2,3,4,5,6,7,8,9,101,111,121,131,141 \ldots

Since chefora number is an odd length palindrome, we can write it as x + d + rev(x) where x is a numeric string without leading zeros and 0 \leq d \leq 9 holds. (Note that here + denotes string concatenation).

So, let us try all candidates for x starting from 0 and for each candidate of x, try all d in range [0, 9] and add f(x, d) to list, where f(x, d) = \text{int}(x+d+rev(x)) where + denotes string concatenation.

For example, when trying x = 24, we get 24042, 24142, 24242, 24342 \ldots

We can intuitively prove that by considering candidates for x in increasing order, and iterating over d in increasing order, f(x, d) are generated in increasing order. So, by considering the first 10^5 tuples of (x, d), we can generate the whole list.

Though it might be sufficient to use strings here, we can actually generate the whole list without using strings by a bit of math, which can be seen from line 7 to line 17 in the editorialist’s solution attached below.

As an exercise, it is quite easy to generate N-th chefora number quite easily in O(log_{10}(N) time directly. See chefora function in tester solution, lines 161 to 169.

Answering queries

We now have all A_i computed in an array, and we need to compute \displaystyle \prod_{i = L+1}^R (A_L)^{A_i} for given L and R where (L < R).

We can write above as \displaystyle (A_L) ^P where \displaystyle P = {\sum_{i = L+1}^R A_i}. So, all we need is subarray sum of range [L+1, R]. Let’s assume \displaystyle P_x = \sum_{i = 1}^x A_i, then answer to our query is A_L ^ {P_R - P_L} \bmod{10^9+7} which can be easily computed using binary exponentiation.

TIME COMPLEXITY

The time complexity is O(MX + Q*log(MOD)) where MX = 10^5 is the size of list.

SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MX = 1e5 + 1;
const int MOD = 1e9 + 7;

int mod_mul(int a, int b, int m) {
    return (a % m * b % m + m) % m;
}

int mod_expo(int a, int b, int m) {
    int res = 1;
    while (b > 0) {
        if (b & 1) res = mod_mul(res, a, m);
        a = mod_mul(a, a, m);
        b >>= 1;
    }
    return res;
}

vector<int> prefix_sums(vector<int> &x) {
    int n = x.size();
    vector<int> ps(n);
    ps[0] = x[0];
    for (int i = 1; i < n; i++) {
        ps[i] = x[i] + ps[i-1];
    }
    return ps;
}

int32_t main() {

    vector<int> chefora(MX);
    for (int i = 1; i < MX; i++) {
        string left = to_string(i);
        string right = left;
        reverse(right.begin(), right.end());
        right = right.substr(1, right.length());
        int num = stoll(left + right);
        chefora[i] = num;
    }

    vector<int> ps = prefix_sums(chefora);

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << mod_expo(chefora[l], (ps[r] - ps[l]), MOD) << endl;
    }
}
Tester's Solution
/* in the name of Anton */

/*
  Compete against Yourself.
  Author - Aryan (@aryanc403)
  Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/

#ifdef ARYANC403
    #include <header.h>
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    //#pragma GCC optimize ("-ffloat-store")
    #include<bits/stdc++.h>
    #define dbg(args...) 42;
#endif

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

long long readInt(long long l, long long r, char endd) {
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true) {
        char g=getchar();
        if(g=='-') {
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g&&g<='9') {
            x*=10;
            x+=g-'0';
            if(cnt==0) {
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd) {
            if(is_neg) {
                x=-x;
            }
            assert(l<=x&&x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l, int r, char endd) {
    string ret="";
    int cnt=0;
    while(true) {
        char g=getchar();
        assert(g!=-1);
        if(g==endd) {
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt&&cnt<=r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
    return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
    return readString(l,r,' ');
}

void readEOF(){
    assert(getchar()==EOF);
}

vi readVectorInt(int n,lli l,lli r){
    vi a(n);
    for(int i=0;i<n-1;++i)
        a[i]=readIntSp(l,r);
    a[n-1]=readIntLn(l,r);
    return a;
}

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vi a;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

lli chefora(lli x){
    lli cur=x;
    x/=10;
    while(x>0){
        cur=cur*10+x%10;
        x/=10;
    }
    return cur;
}

lli pow(lli a,lli p){
    p%=mod-1;
    a%=mod;
    lli ans=1;
    while(p){
        if(p&1)
            ans=(ans*a)%mod;
        p/=2;
        a=(a*a)%mod;
    }
    return ans;
}

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
const lli N = 1e5;
vi a(N+1);
for(lli i=1;i<=N;++i){
    a[i]=chefora(i);
}
dbg(a);
for(lli i=1;i<=N;++i)
    a[i]+=a[i-1];
T=readIntLn(1,1e5);
while(T--)
{
    const lli l=readIntSp(1,N);
    const lli r=readIntLn(l+1,N);
    cout<<pow(a[l]-a[l-1],a[r]-a[l])<<endl;
}   aryanc403();
    readEOF();
    return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class CHEFORA{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int MX = (int)1e5;
        long[] list = new long[1+MX];
        int cnt = 0;
        long mul = 1;
        for(int le = 0; cnt <= MX; le++){
            if(le == mul)mul *= 10;
            for(int mid = 0; mid < 10 && cnt <= MX; mid++){
                long val = (le*10 + mid)*mul + reverse(le);
                list[cnt++] = val;
            }
        }
        long[] sum = new long[1+MX];
        for(int i = 1; i<= MX; i++)sum[i] = sum[i-1]+list[i];
        for(int Q = ni(); Q> 0; Q--){
            int L = ni(), R = ni();
            long ans = pow(list[L], sum[R]-sum[L]);
            pn(ans);
        }
    }
    long MOD = (long)1e9+7;
    long pow(long a, long p){
        long o = 1;
        a %= MOD;
        while(p > 0){
            if((p&1) == 1)o = o*a%MOD;
            a = a*a%MOD;
            p>>=1;
        }
        return o;
    }
    long reverse(long x){
        long rev = 0;
        for(; x > 0; x /= 10)
            rev = rev*10+x%10;
        return rev;
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new CHEFORA().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

3 Likes

can anyone tell me where is the error in this code
#include <bits/stdc++.h>
using namespace std;

static long int m=1e9+7;
long int a[100009],v[100009];

int createPalindrome(int input, int b)
{
int n = input;
int palin = input;

n /= b;
while (n > 0){
    palin = palin * b + (n % b);
    n /= b;
}
return palin;

}

void generatePalindromes(int n){
int number;
int j=1;

int i = 1,l=0;
while ((number = createPalindrome(i, 10)))
{
    a[i]=number;
    v[i]=v[i-1]+a[i];
    i++;
    l++;
    if(l>n)
    break;
}

}

int main()
{
int n = 100009,l,r;
generatePalindromes(n);

int q;
cin>>q;
while(q--)
{
    long long int l,r,res=1;
    cin>>l>>r;
    long int x=v[r]-v[l],base=a[l];
    // cout<<"v[r]-v[l]:"<<v[r]-v[l]<<endl;
    
    while(x>0)
    {
        if(x%2==0)
        {
            base=((base%m)*(base%m))%m;
            x=x/2;
        }
        else
        {
            res=((res%m)*(base%m))%m;
            x=x-1;
        }
      
    }
    cout<<res;
    cout<<endl;
}
return 0;

}

#include
#include<bits/stdc++.h>
using namespace std;

long long chefora(long long n)
{
if(n<=9)
{
return n;
}
long long temp=n,r,sum=0;
n=n/10;
while(n)
{
r=n;
sum=sum10+r;
n=n/10;
}
string str=to_string(temp);
string str1=to_string(sum);
str=str+str1;
temp=stoi(str);
return temp;
}
long long power(long long p,long long n,long long m)
{
if(n==0)
{
return 0;
}
if(n==1)
{
return p;
}
else if(n%2==0)
{
long long r=power(p,n/2,m);
return (r
r)%m;
}
else
{
return(power(p,n/2,m)*power(p,n/2,m)*p)%m;
}
}

int main() {
int q;
cin>>q;
while(q)
{
long long sum=0,l,r;
cin>>l>>r;
vectorv;
for(int i=l+1;i<=r;i++)
{
long long s=chefora(i);
v.push_back(s);
}
for(int i=0;i<v.size();i++)
{
sum+=v[i];
}
cout<<power(l,sum,1000000007)<<endl;
q–;
}
return 0;
}

anyone please tell me what is wrong in this code

Can someone tell me why I got only 30 points, my code was failing for subtask 2!

Here’s my code :

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxN 100008

unsigned int pre[maxN],a[maxN];
ll m = 1000000000+7;

ll power(ll x, ll y)
{
ll res = 1; // Initialize result

// Update x if it is more than or
// equal to p
x = x % m;

while (y > 0) {
   
    // If y is odd, multiply x
    // with the result
    if (y & 1)
        res = (res%m * x%m + m) % m;

    // y must be even now
    y = y >> 1; // y = y/2
    x = (x%m * x%m + m) % m;
}
return res%m;

}

void comp(){

pre[1] = 1 , a[1] = 1;

for(ll i=2;i<=9;i++){

   a[i] = i;
    
   pre[i] = (pre[i-1]%m+a[i]%m)%m;
   

} 

for(ll i=10;i<=100003;i++){

   string s = to_string(i);
    
  string str = to_string((i)/10);
  reverse(str.begin(), str.end());

   s += str;

   ll pp = stoll(s, nullptr, 10); 

  a[i] = pp;
    
  pre[i] = (pre[i-1] + a[i])%m;
 

  //cout << pre[i] << " ";

  //cout << s << " ";

}

}

int main(){

      ll t;  cin >> t; 
       
      comp(); 

      ll L,R;
 
      //ll m = power(10,9)+7;

    //cout << mod(a[1009],m);
          

     for(int i=1;i<=t;i++){

      cin >> L >> R;
    
    ll ans = a[L]%m; 
    
    ll sum = (pre[R]%m-pre[L]%m)%m; 
    
    ll tru = power(ans,sum)%m; 
    
   // tru = tru % m;
    

    //if(tru < 0) tru += m;
    
    cout << tru << endl;
    //  cout << ans << " " << sum << endl;

}

     return 0;
}

Why My Solution is getting accepted partially ,Please Help

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli mod = 1000000007;
typedef vector<lli> vi;
const lli N=1e5;

lli chefora(lli x)
{
    lli cur=x;
    x/=10;
    while(x!=0)
    {
        cur=cur*10+x%10;
        x/=10;
    }
    return cur;
}
// Modular Exponentiation
lli pow(lli a,lli b)
{
    // cout<<a<<" ^ "<<b<<" = ";
    b=b%mod;
    a=a%mod;
    lli ans=1;
    while(b)
    {
        if(b%2!=0)//odd number
        {
            ans=(ans*a)%mod;
        }
        b/=2;
        a=(a*a)%mod;
    }
    // cout<<ans<<"\n";
    return ans;
}
//agar input diye bina run krenge to ye editor to segsiv dega
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    vi a(N+1,0);
    for(lli i=1;i<=N;i++)
    {
        a[i]=chefora(i);
    }
    for(lli i=1;i<=N;i++)
    {
        a[i]+=a[i-1];
    }
    
    lli t;
    cin>>t;
    while(t--)
    {
        lli l,r;
        cin>>l>>r;
        cout<<pow(chefora(l),a[r]-a[l])<<"\n";
    }
    return 0;
}

b=b%mod;this is wrong
correct one is
b=b%(mod-1)

but why we have to do (mod-1)

From the fermat’s little theorem

( (a^(p-1) ) mod p) = 1

Ex:

(3^(77) ) mod 11

from the fermat’s little theorem ((3^10)mod 11) ==1
so,
3^ 77 = (3 ^ 10) * (3 ^ 10) * (3 ^ 10) * (3 ^ 10) * (3 ^ 10) * (3 ^ 10) * (3 ^ 10) * (3 ^ 7)

3^ 77 = 1 * 1 * 1 * 1* 1 * 1 * 1 * (3 ^ 7)
computing 3 ^ 10 is useless because it is already 1
we can get the 7 directly if we do mod with 10
so, 77 mod 10 = 7
finally we are computing only (3 ^ 7) mod 11

1 Like
Q = int(input())
arr = []
arr.append(0)
for i in range(1,10**5+1):
    temp = i
    num = i//10
    while num>0:
        rem = num%10
        temp = temp*10+rem
        num = num//10
    arr.append(temp)
    
sm = []
sm.append(0)
for i in range(1,10**5+1):
    sm.append(sm[i-1]+arr[i])

def power(x,y,p):
    res = 1
    x = x%p
    if x==0:
        return 0
    while y>0:
        if((y&1)==1):
            res = (res*x)%p
        y = y>>1
        x = (x*x)%p
        
    return res

mod = 1000000007
while Q!=0:
    l,r = map(int,input().split())
    res = 1
    prefix = (sm[r]-sm[l])
    base = arr[l]
    print(power(base,prefix,mod))
    Q -= 1

The above python code will help understand the solution better for starters
some useful links to know the concepts involved in solving this problem:
1.Prefix Sum Array - Implementation and Applications in Competitive Programming - GeeksforGeeks
2.Modular Exponentiation (Power in Modular Arithmetic) - GeeksforGeeks
3.Write a program to reverse digits of a number - GeeksforGeeks