문제 설명
N x N 격자가 주어질 때 각 행과 열에 빨간색 하나 파란색 하나를 색칠하는 경우의 수를 구하면 됩니다.
풀이
저는 이 문제를 보고 DP라고 생각하여 열심히 점화식을 구했습니다.
먼저 빨간색을 먼저 색칠해보겠습니다. 아무것도 색칠하지 않은 격자에 빨간색을 색칠하는 경우의 수는 N!입니다.
행, 열에 같은 색이 하나씩 있어야 하므로..
그럼 빨간색의 경우의 수는 구했으니 빨간색이 색칠되어 있을 때 파란색을 색칠하는 경우의 수를 알면 됩니다!!
빨간색을 다 색칠한 N x N 격자에서 파란색을 다 색칠하는 경우의 수를 \(A_N\) 라고 하겠습니다.
먼저 저렇게 색칠한 경우에서 파란색을 첫 번째 열에 파란색을 색칠하겠습니다.
여기에 파란색을 색칠하게 되면 첫 번째 열과 마지막 행은 이제 파란색을 색칠할 수 없으므로 제외하고 보겠습니다.
새로운 형태가 나왔습니다.
이와 같이 한 행과 열이 아무것도 색칠되어 있지 않은 N x N 격자에 파란색을 색칠하는 경우의 수를 \(B_N\) 이라고 하겠습니다.
여기서 \(A_N\)은 첫 번째 열에 (N - 1) 가지를 색칠할 수 있고 색칠한 뒤에는 \(B_{N-1}\)의 형태가 나옵니다.
그러므로 \(A_N = (N-1) \times B_{N-1}\) 입니다.
여기에서는 색칠하는 방법이 2가지로 나뉠 수 있습니다.
우선 아무것도 색칠하지 않은 행에 파란색을 색칠하겠습니다.
-
빨간색이 색칠되어 있는 열에 색칠하기
-
아무것도 색칠 되어있지 않은 열에 색칠하기
1번째 방법을 보겠습니다.
이와 같이 색칠하면 파란색을 색칠한 행과 열은 아까와 같이 제외하면 됩니다.
그렇게 되면 이처럼 아까와 같은 Bn의 형태가 나옵니다.
2번째 방법을 보겠습니다.
행과 열을 지워보겠습니다.
AN의 형태가 나왔습니다.
BN을 색칠하는 방법은 이처럼 2가지로 나눌 수 있고
1번째 방법은 빨간색이 색칠되어 있는 열의 수가 N - 1개입니다.
그러므로 \(B_N = (N-1) * 1번 결과 + 2번 결과\) 입니다.
\(B_N = (N-1) \times B_{N-1} + A_{N-1}\)
\(A_N = (N-1) \times B_{N-1}\)
\(B_N = (N-1) \times B_{N-1} + A_{N-1}\)
구한 두 식으로 \(A_N\) 점화식을 더 간단하게 만들어 보겠습니다.
\(B_N = (N-1) \times B_{N-1} + A_{N-1} = A_N + A_{N-1}\)
\(A_N = (N-1) \times B_{N-1} = (N-1) \times (A_{N-1} + A_{N-2})\)
\(A_N = (N-1) \times (A_{N-1} + A_{N-2})\)
N x N 격자에 빨간색과 파란색을 색칠하는 경우의 수는
\(= N! \times A_N\)
이제 값을 구하면서 모듈러 연산만 잘해주면 됩니다 ㅎㅎ
이 문제의 점화식을 힘들게 구했는데 교란순열을 이용하여 풀면 되고 저 식이 교란순열 식이라고 합니다…
이래서 수학 공부를 해야…
하하하하ㅏ
소스 코드
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define mod ((int)1e9 + 7)
using namespace std;
int main() {
FIO;
int n; cin >> n;
int a = (n != 1), b = 1, c = 0, f = 1; // a = n, b = n-1, c = n-2, f = n!
FOR(i, 3, n)
a = 1LL * (i - 1) * (b + c) % mod, c = b, b = a;
FOR(i, 1, n) f = (1LL * f * i) % mod;
cout << 1LL * f * a % mod << '\n';
return 0;
}