PROBLEM LINK:
Setter: Danylo Mocherniuk
Tester: Radoslav Dimitrov
Editorialist: Teja Vardhan Reddy
DIFFICULTY:
Simple
PREREQUISITES:
Math, fast exponentiation
PROBLEM:
Among all numbers from 0 through 10^K - 1 (lets say i is a number in that range),number of i values having exactly two distinct digits considering all the digits in i and 10^K-i-1.
EXPLANATION
Firstly lets notice that 10^K-1 is 99999.... k times.
Lets say p th digit of i is j. We can now see that p th digit of 10^K-1-i will be 9-j.
Lets say 1st digit (one’s place) of i is j. Now 1st digit of 10^K-i-1 (one’s place) will be 9-j. We can see that j and 9-j are never equal. So now, the two distinct digits must be j and 9-j.
So now from here, we can conclude that digits of i can be j or 9-j only. Now lets prove that all such numbers of this form have exactly 2 digits.
Proof: Wherever i has digit j,10^K-1-i has 9-j. and when i has digit 9-j then 10^K-1-i has j. Also since 1st digit (one’s place) of both numbers cannot be same as seen above. Hence,both j and 9-j occur in both the numbers combined and they are not same.
Now we want to count all such numbers,for each choice of first digit from 0 to 9, rest of the digits have 2 choices each, Hence, with j as 1st digit ,there are 2^{k-1} such number.
Therefore, total numbers that satisfy are (10* 2^{k-1}).
Now we can use fast exponentiation to find 2^{k-1} modulo 10^9+7.
TIME COMPLEXITY
O(log(k))
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 1000 * 1000 * 1000 + 7;
int main()
{
int T;
cin >> T;
while(T--)
{
int K;
cin >> K;
LL ans = 5;
LL dwa = 2;
while(K)
{
if(K & 1)
{
ans *= dwa;
ans %= mod;
}
dwa *= dwa;
dwa %= mod;
K >>= 1;
}
cout << ans << endl;
}
}
Tester's Solution
import sys
def read_line():
return sys.stdin.readline()[:-1]
def read_int():
return int(sys.stdin.readline())
def read_int_line():
return [int(v) for v in sys.stdin.readline().split()]
############
# Solution #
mod = 1000000007
def pw(x, p):
ret = 1
while p:
if p & 1:
ret = ret * x % mod
x = x * x % mod
p >>= 1
return ret;
T = read_int()
for _t in range(T):
K = read_int()
answer = 5 * pw(2, K) % mod
print(answer)
Editorialist's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
ll powe(ll a,ll b){
ll ans=1;
while(b){
if(b%2){
ans*=a;
ans%=mod;
}
a*=a;
a%=mod;
b/=2;
}
return ans;
}
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int k;
cin>>k;
ll ans=powe(2,k);
ans*=5;
ans%=mod;
cout<<ans<<endl;
}
return 0;
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed.