| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 121 | 62 | 47 | 50.538% |
지훈이는 PQ라는 자료구조를 만들었다. 하지만 PQ라는 이름의 특성상 PriorityQueue으로 오해받고는 한다.
PQ 자료구조는 문자 P를 저장하는 큐(Queue)로, 다음 두 명령어를 사용한다.
PP: 문자 P 하나를 PQ 큐 맨 앞에 Push한다.P: PQ 큐 맨 뒤의 문자 P 하나를 pop한다. 단, PQ 큐가 비어 있을 때는 수행할 수 없다.지훈이는 명령어들을 공백 없이 이어 붙이면 P의 나열이 된다는 사실을 알았다. 문득, P가 $N$개 나열된 문자열이 주어졌을 때 이를 유효한 명령어로 해석하는 방법이 총 몇 가지나 될지 궁금해졌다.
처음에 PQ 큐가 비어 있을 때, $N$개의 P로 이루어진 문자열을 유효하게 해석할 수 있는 경우의 수를 구해보자. 비어 있는 PQ 큐에서 pop을 하는 경우 유효하지 않은 해석임을 유의하자.
첫 번째 줄에 테스트 케이스의 개수 $T(1\le T\le 10^6)$가 주어진다.
두 번째 줄에 각 테스트 케이스의 $N$을 의미하는 서로 다른 정수 $N_1,N_2,\cdots ,N_T(1\le N_i\le 10^6)$가 공백으로 구분되어 오름차순으로 주어진다.
첫 번째 줄부터 $T$줄에 걸쳐 각 테스트 케이스 별로 한 줄씩 정답을 $998\, 244\, 353$으로 나눈 나머지를 출력한다. 단, 유효하게 해석할 수 있는 방법이 없다면 대신 -1을 출력한다.
3 5 7 10
2 3 10
$5$개의 P로 이루어진 문자는 아래 $2$가지 방법으로 해석할 수 있다.
PP / PP / PPP / P / PP$7$개의 P로 이루어진 문자는 아래 $3$가지 방법으로 해석할 수 있다.
PP / PP / PP / PPP / PP / P / PPPP / P / PP / PP$10$개의 P로 이루어진 문자는 아래 $10$가지 방법으로 해석할 수 있다.
PP / PP / PP / PP / PPPP / P / PP / P / PP / PPPP / P / PP / PP / P / PPPP / P / PP / PP / PP / PPP / PP / P / P / PP / PPPP / PP / P / PP / P / PPPP / PP / P / PP / PP / PPP / PP / PP / P / P / PPPP / PP / PP / P / PP / PPP / PP / PP / PP / P / P2 999999 1000000
697664704 931479815
University > 고려대학교 > 고려대학교 프로그래밍 경시대회 > 2025 고려대학교 프로그래밍 경시대회 (KCPC) > Div. 1 C번