| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 124 | 75 | 72 | 63.158% |
Bogosort는 정렬이 될 때까지 랜덤 셔플(무작위로 섞기)을 반복하는 정렬 알고리즘으로, 운만 좋다면 어떠한 배열도 $O(n)$의 시간 복잡도로 정렬할 수 있다. 이렇게 사기적인 성능을 가만히 두고 볼 수 없었던 준서는 이를 너프해 안 보고 정렬을 만들었다. 안 보고 정렬은 그 이름대로 배열의 값들을 볼 수 없는 대신 배열의 길이, 원소의 최댓값과 최솟값만 알 수 있다.
구체적으로 어떤 정수 배열 $A$를 안 보고 정렬하는 과정은 다음과 같다.
이때, 1번에서 고르는 배열 $B$는 매번 독립적으로 고른다.
이제 준서는 안 보고 정렬의 성능을 평가하려고 한다. 어떤 배열을 안 보고 정렬을 통해 정렬할 때 1번 단계가 수행되는 횟수의 기댓값을 구해보자.
첫 번째 줄에 테스트 케이스의 개수 $T(1\le T\le 100\, 000)$가 주어진다.
두 번째 줄부터 $T$줄에 걸쳐 각 테스트 케이스마다 한 줄씩 배열의 길이 $N(2\le N\le 10^{18})$, 배열의 최솟값과 최댓값을 의미하는 정수 $L,R(1\le L\le R\le 10^{18})$이 공백으로 구분되어 주어진다.
첫 번째 줄부터 $T$줄에 걸쳐 각 테스트 케이스마다 한 줄씩 해당 배열을 안 보고 정렬을 통해 정렬할 때 1번 단계가 수행되는 횟수의 기댓값을 $998\, 244\, 353$로 나눈 나머지를 출력한다.
기약 분수 $\frac{p}{q}(p\ge 0,q>0,\gcd(p,q) =1)$를 $M$으로 나눈 나머지는 $q^{-1}$가 $q\cdot q^{-1}\equiv 1\pmod M$을 만족하는 정수, 즉 $q$의 $M$에 대한 모듈로 곱셈 역원일 때, $p\cdot q^{-1}\pmod M$로 정의한다. 만약 정수일 경우 $q=q^{-1}=1$이므로 $p\pmod M$를 의미한다. 주어진 조건을 만족하는 모든 가능한 입력에 대해 기댓값이 정수 혹은 분모가 $998\, 244\, 353$의 배수가 아닌 유리수로 나타낼 수 있다.
4 3 1 2 2 1 10 5 1 10 314159265358979323 161803398874989484 271828182845904523
6 2 14670 858154754
첫 번째 테스트 케이스에서 1번 단계 조건을 만족하는 배열 $B$로는 $\left[ 1,1,2 \right]$, $\left[ 1,2,1 \right]$, $\left[ 1,2,2 \right]$, $\left[ 2,1,1 \right]$, $\left[ 2,1,2 \right]$, $\left[ 2,2,1 \right]$이 있으며, 1번 단계는 평균 $6$회 수행된다.
University > 고려대학교 > 고려대학교 프로그래밍 경시대회 > 2025 고려대학교 프로그래밍 경시대회 (KCPC) > Div. 1 F번
University > 고려대학교 > 고려대학교 프로그래밍 경시대회 > 2025 고려대학교 프로그래밍 경시대회 (KCPC) > Div. 2 F번