| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 27 | 3 | 3 | 42.857% |
체육 시간이 되어 $N$명의 학생들이 운동장에 서 있다. 선생님 정원이는 학생들을 키 순서대로 정렬하려고 한다. 현재 학생들은 줄 A에 서 있는데, 정원이는 다음과 같은 방식으로 학생들을 줄 B로 옮기려고 한다.
A에 있는 학생 중 맨 앞에 있는 $1$명 이상의 학생을 임시 줄로 옮긴다.B의 뒤쪽으로 순서를 바꾸지 않고 옮긴다.A에 학생이 모두 없어질 때까지 1 ~ 3단계를 반복한다.정원이는 줄 A에 있는 학생들을 옮기는 방법을 바꾸면 줄 B로 이동하는 학생들의 최종 순서가 바뀔 수 있다는 것을 확인하였다. 정원이는 학생들의 최종 순서로 가능한 경우가 얼마나 있는지 알아보려고 한다. 학생들의 가능한 최종 순서의 가짓수를 구하는 프로그램을 작성하여라.
첫 번째 줄에 학생의 수 $N$이 주어진다.
두 번째 줄에는 학생들의 키 순서를 나타내는 정수 $N$개가 주어진다. $i+1$($0 \leq i < N$)번째 값은 앞에서 $i+1$번째 학생보다 키가 작은 학생 수를 의미하는 $0$ 이상 $N-1$ 이하의 정수이다. 모든 학생의 키는 서로 다르다.
정원이가 학생들을 모두 정렬한 다음 나올 수 있는 학생들의 순서로 가능한 경우의 수를 $998\,244\,353$으로 나눈 나머지를 출력한다.
모든 데이터에 대해서, $1 \leq N \leq 250\,000$ 를 만족한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 1 | $N ≤ 16$ |
| 2 | 1 | $N ≤ 250$ |
| 3 | 1 | 추가 제약조건은 없다. |
5 0 2 1 3 4
2
6 5 4 3 2 1 0
32
9 6 7 8 3 4 5 0 1 2
55
Contest > BOJ User Contest > FunctionCup > FunctionCup 2023 QR번