# CHEFORA - Editorial

Setter: Bharat Singla
Tester: Aryan
Editorialist: Taranpreet Singh

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.

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
#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) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

assert(getchar()==EOF);
}

vi a(n);
for(int i=0;i<n-1;++i)
return a;
}

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
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];
while(T--)
{
cout<<pow(a[l]-a[l-1],a[r]-a[l])<<endl;
}   aryanc403();
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;
void run() throws Exception{
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());}

StringTokenizer st;
}

}

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

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


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

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;
}

#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