| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 24 | 6 | 6 | 75.000% |
길이가 $N$인 순열 $p=(p_1, p_2, \cdots, p_N)$를 생각하자. 즉, $p$는 $1$ 이상 $N$ 이하의 정수들이 정확히 한 번씩 등장하는 수열이다.
이 순열 $p$는 사전에 주어지는 $M$개의 조건을 모두 만족해야 한다. 각 조건은 특정 위치 $i$에 대하여 다음 두 가지 형태 중 하나이다.
주어진 $M$개의 조건을 모두 만족하는 길이 $N$의 순열들의 집합을 $S$라 하자.
이제 집합 $S$에 속한 각 순열 $p$를 오름차순으로 정렬하는 데 드는 비용을 측정하기 위해, 다음 두 가지 연산을 정의한다.
어떤 순열 $p$를 오름차순으로 정렬할 때, 연산 1만을 사용하여 정렬하는 데 필요한 최소 연산 횟수를 $f(p)$라 하고, 연산 2만을 사용하여 정렬하는 데 필요한 최소 연산 횟수를 $g(p)$라 하자.
당신의 목표는 조건을 만족하는 모든 순열 $p \in S$에 대하여, $f(p)$와 $g(p)$의 곱의 합을 구하는 것이다. 다음 식의 값을 $998\,244\,353$으로 나눈 나머지를 계산해 보자.
$$\sum_{p\in S} f(p) \cdot g(p)$$
첫 번째 줄에 두 개의 정수 $N$, $M$이 공백으로 구분되어 주어진다.
다음 $M$개의 줄에는 두 개의 정수 $t$, $i$가 공백으로 구분되어 주어지며, 이는 다음을 의미한다.
$\sum_{p\in S} f(p)\cdot g(p)$를 $998\, 244\, 353$으로 나눈 나머지를 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $N \le 8$ |
| 2 | 50 | $N \le 250$ |
| 3 | 20 | $M = 0$ |
| 4 | 20 | 추가 제약 조건 없음 |
3 1 2 3
12
$S = \{(1,3,2),(2,3,1),(3,1,2),(3,2,1)\}$이다. 각 순열에 대한 $f$와 $g$ 값은 다음과 같다.
$1\times 1 + 2\times 2 + 2\times 2 + 3\times 1 = 12$를 출력한다.
3 1 1 3
0
조건을 만족하는 순열이 없다. 따라서 $0$을 출력한다.
6 3 1 3 2 4 1 5
938
School > 한국과학영재학교 > 2026 KSA Automata Winter Contest K번