Submission #286159

#	Time	Username	Problem	Language	Result	Execution time	Memory
286159		erray	Rack (eJOI19_rack)	C++14	100 / 100	1 ms	384 KiB

rack

// author: erray
#include<bits/stdc++.h>
 
using namespace std;

const int mod = (int) 1e9 + 7;

long long power(long long b, long long p) {
  long long res = 1;
  while (p) {
    if (p & 1) (res *= b) %= mod;
    (b *= b) %= mod;
    p >>= 1;
  }
  return res;
}

vector<long long> fac(1, 1), inv_fac(1, 1);
long long C(int x, int y) {
  if (x < y) return 0;
  while ((int) fac.size() <= x) {
    fac.push_back((fac.back() * (int) fac.size()) % mod);
    inv_fac.push_back(power(fac.back(), mod - 2));
  }
  return fac[x] * inv_fac[y] % mod * inv_fac[x - y] % mod;
}
long long P(int x, int y) {
  if (x < y) return 0;
  while ((int) fac.size() <= x) {
    fac.push_back((fac.back() * (int) fac.size()) % mod);
    inv_fac.push_back(power(fac.back(), mod - 2));
  }
  return fac[x] * inv_fac[y] % mod;
}
 
int main () {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  long long k;
  cin >> n >> k;
  --k;
  long long ans = 1;
  for (int i = 0; i < 64; ++i) {
    if (k & (1LL << i)) {
      (ans += power(2, n - 1 - i)) %= mod;
    }              
  }
  cout << ans << '\n';
}

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