Keep It Cool

시간 제한1초메모리 제한512 MB

요약

모든 쌍 (a, b)를 배열하는 순열 중 세 쌍 사이 순서 규칙과 m개의 순서 제약을 지키는 경우의 수를 998244353으로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 비트 연산
정답자: 아직 제출이 없습니다

문제

$1 \leq a < b \leq n$ 을 만족하는 모든 쌍 $(a, b)$ 의 집합을 생각하자. 이 쌍들을 모두 나열한 순열은 $1 \leq a < b < c \leq n$ 인 임의의 $a$ , $b$ , $c$ 에 대해 쌍 $(a, c)$ 가 순열에서 $(a, b)$ 와 $(b, c)$ 사이에 놓일 때 균형 잡힌 순열이라고 한다. 즉 세 쌍은 $(a, b), (a, c), (b, c)$ 순서로 나오거나 $(b, c), (a, c), (a, b)$ 순서로 나와야 한다.

순열에는 추가로 $m$ 개의 제약이 있다. $i$ 번째 제약은 쌍 $(a_i, b_i)$ 가 쌍 $(c_i, d_i)$ 보다 순열에서 앞에 나와야 한다는 것이다. 이 $m$ 개의 제약을 모두 만족하는 균형 잡힌 순열의 개수를 구하라.

입력

첫 줄에 정수 $n$ 과 $m$ ( $2 \le n \le 10$ , $0 \le m \le 10$ )이 주어진다. 이어지는 $m$ 개의 줄에는 정수 $a_i$ , $b_i$ , $c_i$ , $d_i$ ( $1 \le a_i < b_i \le n$ , $1 \le c_i < d_i \le n$ )가 주어진다. 쌍 $(a_i, b_i)$ 와 $(c_i, d_i)$ 는 서로 다르다.

출력

모든 $i$ 에 대해 $(a_i, b_i)$ 가 $(c_i, d_i)$ 보다 먼저 나오는 균형 잡힌 순열의 개수를 소수 $998\,244\,353$ 으로 나눈 나머지로 출력하라.

힌트

두 번째 입력에서 조건을 만족하는 순열은 $(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)$ 와 $(1,2), (1,3), (2,3), (1,4), (2,4), (3,4)$ 이다.

예제2

예제 1
입력
```
2 0
```
예상 출력
```
1
```
예제 2
입력
```
4 3
1 2 2 3
1 2 3 4
2 3 3 4
```
예상 출력
```
2
```