| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 69 | 57 | 43 | 84.314% |
하지만 KCPC 운영을 위해서는 세진이는 운영진 현황을 안 세진 채로 둘 순 없다.
KCPC 2025의 운영진은 KAIST 소속의 동우, 컴퓨터학과(Computer Science) 소속 동현이, 물리학과(Physics) 세진이, 사이버국방학과(Cyber Defense) 지훈(가명)이 등 다양한 소속의 사람들로 구성되어 있다.
세진이는 KCPC 운영진의 자리를 배치하려고 한다. 대회 운영진들이 있을 방에는 $N\times M$개의 자리가 $N$행 $M$열의 모양으로 배치되어 있으며, 세진이는 각 자리에 K, C, P 중 하나를 배치할 것이다. 이때 임의의 연속된 두 행과 연속된 두 열로 이루어진 $2\times 2$ 자리에 대해, K, C, P가 각각 $1$개, $2$개, $1$개로 구성되어 있어야 한다.
$N$과 $M$이 주어졌을 때 세진이가 조건에 맞게 배치할 수 있는 경우의 수를 구해보자.
첫 번째 줄에 테스트 케이스의 개수 $T(1\leq T\leq 100\, 000)$가 주어진다.
두 번째 줄부터 $T$줄에 걸쳐 각 테스트 케이스 별로 한 줄씩 정수 $N,M(2\leq N,M\leq 100\, 000)$이 공백으로 구분되어 주어진다.
첫 번째 줄부터 $T$줄에 걸쳐 각 테스트 케이스 별로 한 줄씩 정답을 $998\, 244\, 353$로 나눈 나머지를 출력한다.
2 2 2 3 4
12 50
$N=2$, $M=2$의 경우 아래와 같이 $12$가지의 가능한 배치가 있다.
$N=3$, $M=4$의 경우 아래와 같이 $50$가지의 가능한 배치가 있다.
5 22 55 14 44 29 33 54 72 64 50
640851440 260044614 285458402 114348170 670665702
10 99919 12635 46569 92101 87047 85638 34674 91051 53804 65650 55973 84926 90893 44625 83971 98077 13120 95724 74687 81487
935738495 229565321 888256074 105871422 327288010 712182018 606333518 264331652 185098346 881744380
University > 고려대학교 > 고려대학교 프로그래밍 경시대회 > 2025 고려대학교 프로그래밍 경시대회 (KCPC) > Div. 1 J번
University > 고려대학교 > 고려대학교 프로그래밍 경시대회 > 2025 고려대학교 프로그래밍 경시대회 (KCPC) > Div. 2 J번