This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
unordered_map<long long, long long> powers;
const int MOD = 1e9+7;
long long int PowerTwo(long long int exponent){
if(powers.find(exponent) != powers.end()) return powers[exponent];
long long semiAns = PowerTwo(exponent/2);
long long ans = (semiAns*semiAns)%MOD;
if(exponent%2) {
ans*= 2;
ans%=MOD;
}
return powers[exponent] = ans;
}
long long getPos(long long int n, long long int k){
if(k == 1) return 1;
if(k%2){
return getPos(n-1, k/2 +1);
}
else{
long long semiAns = PowerTwo(n-1);
long long ans = (semiAns + getPos(n-1, k/2))%MOD;
return ans;
}
}
int main(){
powers[0] = 1;
powers[1] = 2;
powers[2] = 4;
long long int n, k;
cin >> n >> k;
cout << getPos(n, k)<< endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |