| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 25 | 10 | 8 | 40.000% |
길이가 $N$인 수열 $A_1, A_2, \cdots, A_N$이 주어진다. 다음 $Q$개의 쿼리를 수행하는 프로그램을 작성하여라.
여기서 $C(n) = \frac{(2n)!}{n!(n+1)!}$으로 정의되는 카탈란 수이다.
이 문제의 수열과 쿼리를 생성하기 위한 $N$, $Q$, $seed$가 주어진다. 이후 각 수열과 쿼리는 유사 난수 생성기 Splitmix64로 생성된다. 각 수열과 쿼리를 만드는 방법은 다음과 같으며, 언어별 구현은 노트를 참고하여라. (C, C++, Java, Python, Rust, Ruby)
첫 번째 줄에 공백으로 구분된 세 정수 $N, Q, seed$가 주어진다. $(2 \le N \le 10^5;$ $1 \le Q \le 10^5;$ $1 \le seed \le 10^{18})$
문제의 방법으로 수열과 쿼리를 생성했을 때 $t_j$가 $3$ 혹은 $4$인 쿼리가 $1$개 이상 주어짐이 보장된다.
$t_j$가 $3, 4$인 쿼리에 대해, 계산된 값을 한 줄에 하나씩 출력한다.
5 7 1234567891011121
69857618 553213141 174991376 892725649
이 예제에서 사용된 수열 $A$는 다음과 같다.
$A = [265\,283, 232\,568, 326\,146, 24\,477, 150\,555]$
이 예제에 사용된 쿼리는 다음과 같다.
5 7 2025
957172995 391405023 582105817 782813783 527493019
이 예제에서 사용된 수열 $A$는 다음과 같다.
$A = [100\,216, 914\,117, 715\,218, 727\,500, 443\,111]$
이 예제에 사용된 쿼리는 다음과 같다.
다음은 각 언어별로 문제의 데이터 생성 방법을 구현한 파일이다.
generate(int32_t N, int32_t Q, uint64_t seed)를 호출한다.d에 대해 $A_i$는 d.arr[i]에, $t_j, l_j, r_j, x_j$은 d.query[j][0], d.query[j][1], d.query[j][2], d.query[j][3]에 저장되어 있다.
d의 타입은 data, 각 정수의 타입은 int32_t이며, d.arr[0] 혹은 d.query[0]은 문제의 수열 혹은 쿼리를 저장하고 있지 않음에 유의하여라.d에 대해 메모리를 해제하기 위해서는 free_data(d)를 호출한다.Generate(int32_t N, int32_t Q, uint64_t seed)를 호출한다.d에 대해 $A_i$는 d.arr[i]에, $t_j, l_j, r_j, x_j$은 d.query[j][0], d.query[j][1], d.query[j][2], d.query[j][3]에 저장되어 있다.
d의 타입은 Data, 각 정수의 타입은 int32_t이며, d.arr[0] 혹은 d.query[0]은 문제의 수열 혹은 쿼리를 저장하고 있지 않음에 유의하여라.generate(int n, int q, long seed)를 호출한다.d에 대해 $A_i$는 d.arr[i]에, $t_j, l_j, r_j, x_j$은 d.query[j][0], d.query[j][1], d.query[j][2], d.query[j][3]에 저장되어 있다.
d의 타입은 data, 각 정수의 타입은 int이며, d.arr[0] 혹은 d.query[0]은 문제의 수열 혹은 쿼리를 저장하고 있지 않음에 유의하여라.generate(n: int, q: int, seed: int)를 호출한다.d에 대해 $A_i$는 d.arr[i]에, $t_j, l_j, r_j, x_j$은 d.query[j][0], d.query[j][1], d.query[j][2], d.query[j][3]에 저장되어 있다.
d의 타입은 Data, 각 정수의 타입은 int이며, d.arr[0] 혹은 d.query[0]은 문제의 수열 혹은 쿼리를 저장하고 있지 않음에 유의하여라.generate(n: usize, q: usize, seed: u64)를 호출한다.d에 대해 $A_i$는 d.arr[i]에, $t_j, l_j, r_j, x_j$은 d.query[j][0], d.query[j][1], d.query[j][2], d.query[j][3]에 저장되어 있다.
d의 타입은 Data, 각 정수의 타입은 usize이며, d.arr[0] 혹은 d.query[0]은 문제의 수열 혹은 쿼리를 저장하고 있지 않음에 유의하여라.generate(n, q, seed)를 호출한다.n, q, seed의 타입은 Integer이다.d에 대해 $A_i$는 d.arr[i]에, $t_j, l_j, r_j, x_j$은 d.query[j][0], d.query[j][1], d.query[j][2], d.query[j][3]에 저장되어 있다.
d의 타입은 Data_, 각 정수의 타입은 Integer이며, d.arr[0] 혹은 d.query[0]은 문제의 수열 혹은 쿼리를 저장하고 있지 않음에 유의하여라.Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2025. 02. Ex번