BOJ-14578 영훈이의 색칠공부

필요한 지식

1. 교란순열

접근

• 교란순열을 처음 알게된 문제다.

• 각 행과 열에는 빨간색과 파란색이 한번씩만 칠해져야할때, 모든경우의 수를 1e9+7로 모듈러 연산한 값을 출력해야한다.

• 먼저 파란색만 행과 열이 겹치지 않게 칠한다고 했을 때 n X (n-1) X (n-2) X ... X 1 = n! 의 경우의 수가 나온다.

• 문제에 조건에 맞게 칠해진 파란색칸의 열을 b1~bn, 그리고 문제에 조건에 맞게 빨간색이 칠해질 칸의 열을 r1~rn 이라고 하고, bi와 ri의 행은 i행으로 같다고 했을 때 r1 != b1, r2 != b2, ... , rn != bn인 칸에 칠해져야한다.

• 이를 교란순열이라고 한다. 교란순열에 대한 내용은 참고부분에 링크를 달아놨다. 예시가 잘 설명되어있다.

• 교란순열의 점화식은 D[n] = D[n-1] + D[n-2](D[0] = 1, D[1]=0) 이다.

• 따라서 정답은 파란색이 배치될 경우 X 빨간색의 교란순열 수, n! X D[n]이 된다.

코드(C++)

#include <iostream>
#define MOD 1000000007
using namespace std;
typedef long long ll;

ll d[100002], f = 1;
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n; cin >> n;
	d[1] = 0, d[0] = 1;
	for (ll i = 2; i <= n; i++) {
		f *= i, f %= MOD;
		d[i] = (i - 1) * (d[i - 1] + d[i - 2]) % MOD;
	}
	cout << (f * d[n]) % MOD;
	return 0;
}

---

참고

• 교란순열에 대하여 - jjycjn

---

결과