제출 #1195347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195347		Johan	Rack (eJOI19_rack)	C++20	100 / 100	0 ms	328 KiB

rack

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
  
const int MAX = 3e5 + 6;
const int LOG = 26;
const int inf = 1e18;
const int mod = 1e9 + 7;
const int block = 320;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int pow(int x){
	int cnt = 0;
	while(x > 1){
		x /= 2;
		cnt++;
	}
	return cnt;
}
int binpow(int a, int b){
	int res = 1;
	while(b != 0){
		if(b % 2 == 1){
			res *= a;
			res %= mod;
		}
		a *= a;
		a %= mod;
		b /= 2;
	}
	return res;
}
void _(){
	int n, k;
	cin >> n >> k;
	vector < int > cur;
	for(int i = 0; i <= 60; i++)
		cur.push_back(pow(2, i));
	int tot = 0;
	while(k > 1){
		int ans;
		for(int i = 0; i <= 60; i++){
			if(cur[i] >= k)	break;
			ans = cur[i];
		}
		int power = pow(ans);
//		cout << tot << '-';
		int x = binpow(2, n - power - 1) % mod;
//		cout << n - power - 1 <<  ' ' << x << endl;
		tot = (tot + x) % mod;
		k -= ans;
	}
	cout << (tot + 1) % mod << endl;
}
 
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t = 1;
//	cin >> t;
	while(t--)  _();
}

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