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. 