가짜 퀵소트
시간 제한2초메모리 제한512 MB
재귀 깊이 제한 k가 있는 잘못된 퀵소트를 크기 n의 균등 무작위 순열에 실행했을 때 생기는 역전 수의 기댓값에 n!을 곱한 값을 998244353으로 나눈 나머지를 구한다.
문제
Bob은 아래와 같이 가짜 QuickSort를 구현했다. Bob이 1, 2, . . . , n을 같은 확률로 섞은 순열 p = [p1, p2, . . . , pn]을 무작위로 골라 QuickSort(p, 1, n, k)를 호출했을 때, 호출 후 p의 역전 개수의 기댓값은 얼마일까?
a fake QuickSort implementation
1: function QuickSort(A, l, r, h) ▷ Elements in A would be modified
2: if h > 1 and l < r then
3: m ← Partition(A, l, r)
4: QuickSort(A, l, m - 1, h - 1)
5: QuickSort(A, m + 1, r, h - 1)
6: function Partition(A, l, r) ▷ Elements in A would be modified
7: i ← l
8: j ← r
9: m ← ⌊(l+r)/2⌋
10: pivot ← Am
11: Am ← Ai
12: while i < j do
13: while i < j and Aj ≥ pivot do
14: j ← j - 1
15: if i < j then
16: Ai ← Aj
17: while i < j and Ai < pivot do
18: i ← i + 1
19: if i < j then
20: Aj ← Ai
21: Ai ← pivot
22: return i
순열 [p1, p2, . . . , pn]의 역전 개수는 1 ≤ u < v ≤ n이고 pu > pv인 정수 쌍 (u, v)의 개수이다.
정밀도 문제를 피하기 위해, n의 팩토리얼 n!과 이 기댓값의 곱을 998244353으로 나눈 나머지를 출력한다. 이 값은 정수이다.
입력
입력은 여러 테스트 케이스로 이루어진다. 첫째 줄에는 테스트 케이스의 수를 나타내는 정수 T가 주어진다. 다음 줄부터 각 테스트 케이스가 주어진다.
각 테스트 케이스는 정수 n과 k가 있는 한 줄로 이루어진다.
출력
각 테스트 케이스마다 “Case #x: y”를 한 줄에 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 해당 테스트 케이스의 답이다.
제한
- 1 ≤ T ≤ 3 × 105
- 1 ≤ n, k ≤ 6000