# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
288640 | 2020-09-01T17:32:23 Z | Benmath | Rack (eJOI19_rack) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h> using namespace std; long long int solve(long long int step[],long long int b,long long int n,long long int mod){ long long int step1=1; long long int x,y; long long int b11=b; long long int b1; if(b11%2==0){ y=(b11-2)/2; }else{ y=(b11-1)/2; } if(b11==1){ return 1; } if(b11==2){ return step[n-1]+1; } int mi=0; for(int i=1;i<=n;i++){ if(i!=1){ step1=(step*2)%mod; mi++; } if((y-step1)<step1 and (y-step1)>=0){ b1=y-step1; break; } } b1=b1%mod; if(b11%2==0){ return ( solve(step,b1+1,mi+1,mod)*step[n-2-mi]+step[n-1]+1)%mod; }else{ return (solve(step,b1+1,mi+1,mod)*step[n-2-mi]+1)%mod; } } int main(){ int n; cin>>n; long long int k; cin>>k; long long int mod=1000000007; k=k%mod; long long int step[n+1]; step[0]=1; for(int i=1;i<=n;i++){ step[i]=(step[i-1]*2)%mod; } if(k==1){ cout<<1; }else if(k==2){ cout<<step[n-1]+1; }else{ long long int k1; cout<<solve(step,k,n,mod); } }