금지된 카드 배열
골드 II의견: 0
카드 \(1, 2, \ldots, N\)을 한 줄로 늘어놓으려 한다. 위치 \(i\)에 카드 \(j\)를 놓는 것을 '\((i, j)\) 금지 쌍'으로 지정할 수 있다. 위치는 왼쪽 첫 번째를 \(1\)번으로 한다.
\(M\)개의 금지 쌍이 주어질 때, 어떤 금지 쌍도 만족하지 않는 카드 배열(순열)의 수를 \(10^9+7\)로 나눈 나머지를 구하여라. 모든 금지 쌍에서 위치 번호는 서로 다르고, 카드 번호도 서로 다름이 보장된다.
- \(1 \le N \le 100\,000\)
- \(0 \le M \le 20\)
- 모든 금지 쌍의 위치 \(p_i\)는 서로 다르다. (\(1 \le p_i \le N\))
- 모든 금지 쌍의 카드 번호 \(v_i\)는 서로 다르다. (\(1 \le v_i \le N\))
첫째 줄에 카드의 수 \(N\)과 금지 쌍의 수 \(M\)이 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 금지 쌍 \((p_i, v_i)\)가 한 줄에 하나씩 주어진다.
조건을 만족하는 순열의 수를 \(10^9+7\)로 나눈 나머지를 출력한다.
3 2
1 1
2 2
3
금지 쌍 \((1,1)\): 위치 \(1\)에 카드 \(1\)을 놓지 않는다; \((2,2)\): 위치 \(2\)에 카드 \(2\)를 놓지 않는다. 포함 배제: \(3! - 2! - 2! + 1! = 3\).
4 4
1 2
2 1
3 4
4 3
9
카드 \([1..4]\)를 \(4\)자리에 놓되 네 금지 위치를 피하는 경우의 수. 포함 배제로 \(4! - 4\cdot3! + 5\cdot2! - 2\cdot1! = 14\).
riseoj 작성
출처 Original
평가 및 의견
금지된 카드 배열
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
금지된 카드 배열