oj.uz

답안 #1112009

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1112009 2024-11-13T13:53:21 Z vjudge1 Rack (eJOI19_rack) C++17
100 / 100
 1 ms 504 KB 
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define nmod(a, b) (((a%b)+b)%b) // stands for [n]atural [mod], as in "will always return a natural number", should be used in case of negative
#define a2b(a, b) (a << b) // a*2^b
#define bit(a, b) ((a >> b) & 1) // bth bit from the right, starts at zero
using namespace std;
template<class T> using vec = vector<T>;

const int INFTY = (1LL << 63) - 1;
const int NNFTY = 1LL << 63;
const int mod = 1'000'000'007;

int csp(int a, int k) { // a's closest smaller power of k
    int n = 1;
    while (a > 1) n *= k, a /= k;
    return n;
}

int binpow(int x, int y) {
    if (y < 0) return binpow(x, mod - 1 + y); // allows for binpow(x, -1)
    if (y == 0 || x == 1) return 1;
    if (y == 1) return x%mod;
    if (y % 2 == 0) return binpow((x*x)%mod, y/2);
    return (x*binpow(x, y - 1))%mod;
}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, k, ans = 0; cin >> n >> k;
    k--;
    while (k > 0) {
        int m = csp(k, 2);
        ans += (binpow(2, n) * binpow((2*m)%mod, -1))%mod;
        k -= m;
    }
    cout << (ans + 1) % mod;
}

Compilation message

rack.cpp:10:31: warning: integer overflow in expression of type 'long long int' results in '9223372036854775807' [-Woverflow]
   10 | const int INFTY = (1LL << 63) - 1;
      |                   ~~~~~~~~~~~~^~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 504 KB Output is correct
15 Correct 1 ms 336 KB Output is correct