취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 8478번 문제인 Chessboard이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/8478

조건을 만족하는 룩의 배치는 1번부터 \(n\)번까지의 룩이 차례대로 몇 번째 행에 있는지, 몇 번째 열에 있는지를 나타내는 두 순열은 각각 교란순열(derangement;subfactorial)을 이룬다는 것을 어렵지 않게 관찰할 수 있다. 그리고 조금만 더 생각하면 그 역도 성립함을 관찰할 수 있다. 따라서 문제의 답은 크기가 \(n\)인 교란순열의 개수의 제곱을 \(m\)으로 나누어 구할 수 있다.

교란순열의 값을 구하는 대표적인 방법으로는 포제원리(포함-배제의 원리; Inclusion-Exclusion Principle)를 이용하는 것이 있다. 이를 이용하면 크기가 \(n\)인 교란순열의 개수는 \(\binom{n}{0}(n-0)! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \cdots\) 와 같은 형태로 계산할 수 있다. 앞의 이항계수는 확실하게 위치를 고정시킬 원소를 고르는 경우의 수, 뒤의 팩토리얼은 남은 수를 나열하는 과정으로 해석하자.

구하는 값은 답을 \(m\)으로 나눈 나머지이므로 계산해볼 필요가 있는 항의 개수가 \(m\)개 이하임을 관찰하자. 뒤의 팩토리얼의 값을 작은 값부터 차례대로 살펴볼 때 그 값이 \(m\)의 배수가 되는 순간 남은 항을 고려할 필요가 없어지기 때문이다.

글쓴이는 위의 저 식을 더 정리할 수 있다는 것을 놓쳐 처음에는 Extended Euclidean Algorithm을 활용해 문제를 지저분하게 풀었었다. 그런 것 필요 없이 위의 식의 각 항은 더 깔끔하게 정리할 수 있으므로 잘 정리해서 문제를 해결하자.

아래는 제출한 소스코드이다.

//derangement
//iktk님 풀이 보고 다시 풀기
#include <iostream>
using namespace std;
typedef long long ll;
typedef __int128 lll;

ll N, M;
lll ans, V = 1, sgn;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	if (N & 1) sgn = -1;
	else sgn = 1;
	for (int i = 0; i <= N; i++) {
		if (!V) break;
		ans += V * sgn;
		V = V * (N - i) % M;
		sgn *= -1;
	}

	ans %= M;
	if (ans < 0) ans += M;
	
	cout << (ll)(ans * ans % M);
}

랜덤 마라톤 · 코스 7 - F번