#include <iostream>
using namespace std;
const long long mod = 1e9 + 7;
long long walkLeft(long long node, int layer, int n)
{
if(layer==n+1) return node%mod;
return walkLeft((node*2)%mod, layer+1, n);
}
long long revNum(long long x, int bitCnt)
{
long long res = 0;
for(int bit = 0;bit<bitCnt;bit++)
res += (((x>>bit)&1)<<(bitCnt-bit-1));
return res;
}
int main()
{
long long n, k;
cin >> n >> k;
if(k==1)
{
cout << "1" << '\n';
return 0;
}
k--;
int layer;
for(layer = 1;layer<=n;layer++)
{
long long maxNum = (1LL<<(layer)) - 1;
if(k<=maxNum) break;
}
long long start = (1LL<<(layer-1));
long long kLeft = k - ((1LL<<(layer-1)) - 1) - 1;
long long node = start + revNum(kLeft, layer-1);
node %= mod;
cout << walkLeft(node*2+1, layer+1, n) - (1LL<<n) + 1 << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |