시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1536 MB | 20 | 11 | 11 | 57.895% |
수열 $a_{1}, \cdots, a_{n}$의 inversion이란 $i < j, a_{i} > a_{j}$를 만족하는 순서쌍 $(i,j)$의 개수이다.
$1, \cdots, n$의 순열 중 inversion이 $k$개인 것의 개수를 $I(n, k)$라고 하자.
소수 $P = 10^{6} + 3$에 대해, $n, k$가 주어졌을 때 $I(n, k)$를 $P$로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력의 첫 줄에 테스트 케이스의 개수 $T$가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 $n, k$가 공백을 사이에 두고 주어진다.
테스트 케이스마다 한 줄에 $I(n, k)$를 $P$로 나눈 나머지를 출력한다. $P = 10^{6} + 3$은 소수이다.
10 10 2 10 4 10 6 10 8 10 10 10 12 10 14 10 16 10 18 10 20
44 440 2298 8095 21670 47043 86054 135853 187959 230131
Contest > BOJ User Contest > IDTcup > 제 3회 IDTcup E번