Submission #699641

#	Time	Username	Problem	Language	Result	Execution time	Memory
699641		bane	Rack (eJOI19_rack)	C++17	100 / 100	7 ms	7892 KiB

rack

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<deque>
#include<map>
#include<set>
#include<unordered_set>
#include<math.h>
//#include<bits/stdc++.h>
using namespace std;
 
#ifdef LOCAL
    #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
    #define eprintf(...) 42
#endif
 
#define pb push_back
#define mp make_pair
#define ins insert
#define popb pop_back
#define popf pop_front
#define ft front
#define bk back
#define fr first
#define sc second
using ll = long long;
using ld = long double;
using db = double;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<ld,ld>;
using str = string;
const int NAX = (int)1e5 + 1;
const int MOD = (int)1e9 + 7;

template<class V, int NV>class SegmentTree{
public:
    
};

ll compute(ll b, ll p){
    ll res = 1;
    while(p){
        if (p & 1)res = (res * b) % MOD;
        b = (b * b)%MOD;
        p>>=1;
    }
    return res;
}
//2^1, ,
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll a, b;
    cin >> a >> b;
    ll ps[a + 1];ps[0] = 1;
    for (int i = 1; i<=a; ++i) ps[i] = (ps[i - 1] * 2)%MOD;
    function<ll(ll n, ll k)>pos = [&](ll n, ll k){
        if (k == 1)return 1LL;
        if (k % 2) return (ll)pos(n - 1, k / 2 + 1)%MOD;
        else return (ll)(ps[n - 1] + pos(n - 1, k / 2)%MOD)%MOD;
    };
    cout<<pos(a,b)%MOD;
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 60 / 60