| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 120 | 35 | 25 | 25.773% |
길을 걸어가던 찬우는 바닥에서 1ドル$부터 2ドルN$까지의 정수가 차례로 쓰인 2ドルN$개의 돌들을 발견했다. 질서정연하게 정렬되어있는 돌들이 불편하게 느껴진 찬우는 돌의 순서를 마음대로 바꿔버리기로 했다! 그는 2ドルN$개의 돌들을 2ドル$개씩 짝지어 $N$개의 쌍을 만든 후, 각각의 쌍에서 짝지어진 두 돌의 위치를 바꿔 새로운 돌의 수열 $\{a_1,a_2,\ldots ,a_{2N}\}$을 만들어버렸다.
자신의 손으로 순서가 엉망이 되어버린 돌들을 보며 흡족해하고 있던 찬우는 돌들을 보다가 재미있는 특징을 발견했는데, 바뀌어 버린 수열의 최장 감소 부분 수열의 길이가 2ドル$밖에 되지 않는다는 것이었다. 이 수열이 신기했던 찬우는 이를 사진으로 남기려고 했으나, 하필 배터리를 다 쓴 탓에 대신 자신이 짝지은 한 쌍의 돌 $(X,Y)$을 가져가기로 했다.
집에 돌아온 찬우는 방금 전 만든 수열을 복원하고 싶어졌지만, 자신이 가져온 돌 $X$와 $Y$를 짝지었다는 것과, 돌의 총 개수 2ドルN,ドル 그리고 바꿨던 돌의 수열의 최장 감소 수열의 길이가 2ドル$였다는 사실 말고는 기억나는 것이 없다. 돌의 개수 2ドルN$과 가져온 돌의 쌍 $X,ドル $Y$가 주어질 때, 조건을 만족하는 돌의 수열이 얼마나 많은지 알아보자!
첫 번째 줄에 $N,X,Y$가 공백으로 구분되어 주어진다. (1ドル\le N\le 500\ 000; 1\leq X,Y\leq 2N; X\neq Y$)
조건을 만족하는 돌의 수열의 개수를 998ドル,円 244,円 353$으로 나눈 나머지를 출력한다.
4 5 6
2
$(1, 3),ドル $(2, 4),ドル $(5, 6),ドル $(7, 8)$을 쌍으로 묶어 수열 $\{3, 4, 1, 2, 6, 5, 8, 7\}$을 만들거나, $(1, 2),ドル $(3, 4),ドル $(5, 6),ドル $(7, 8)$을 쌍으로 묶어 수열 $\{2, 1, 4, 3, 6, 5, 8, 7\}$을 만드는 경우에만 최장 감소 수열의 길이가 2ドル$가 된다. 그 외의 방법으로 돌을 짝지어 새로운 수열을 만든 경우에는 $(5, 6)$이 한 쌍으로 묶이지 않았거나, 최장 감소 수열의 길이가 2보다 커지게 되어 문제의 조건을 만족하지 않기 때문에, 가능한 돌의 수열의 개수는 2ドル$개가 된다.
어떤 수열에서 몇 개의 수들을 제거해서 만든 부분 수열을 만들 수 있다. 이때 만들어진 부분 수열 중 내림차순으로 정렬된 가장 긴 부분 수열을 최장 감소 부분 수열이라고 한다.