oj.uz

Submission #286159

# Submission time Handle Problem Language Result Execution time Memory
286159 2020-08-30T07:38:12 Z erray Rack (eJOI19_rack) C++14
100 / 100
 1 ms 384 KB 
// 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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct