박성원

문제 링크

문제를 읽은 당신은 머리가 살짝 어지러워진다. ‘수의 크기가 $10^{50}$?? 이게 뭐지? 그럼 수가 10개면 완성된 수는 500자리야??’ ‘아니 그리고 같은 수를 조합해도 조합된 수의 순서에 따라서 나눠떨어지는지 여부가 달라지는거 아니야? 뭐가 인자지?’ ‘문제 이름이 왜 박성원이야? 박성원이 누군데?‘

발상

핵심은 정답 순열의 개수를 구하는 것이다. 정답 순열 수만 구한다면 확률 기약 분수는 $\gcd$를 통해 쉽게 구할 수 있다. 문제는 주어지는 수들의 크기 제한이 $10^{51}-1$으로 매우 크다. 따라서 수 자체를 인자로 사용하기는 힘들다. 그에 비해 $k$의 크기 제한은 99로 비교적 매우 작다. 나눠떨어지는지 여부만 검사하면되니 수 자체는 사용하지 않고 나머지만 사용해서 코드를 작성할 수 있을 것 같다. 수를 이어붙일 때 나머지가 어떻게 바뀌는지 생각해보자. 이 부분에서 약간의 수학적 직관이 필요한데, 다음과 같다.

어떤 수 $ABCDE$를 $AB000$와 $00CDE$로 분리했을 때, $ABCDE$를 $k$로 나눈 나머지 $r$은 $AB$를 $k$로 나눈 나머지 $r_1$, $CDE$를 $k$로 나눈 나머지 $r_2$에 대해 $r_{1}00r_2$를 $k$로 나눈 나머지와 같다. $AB-r_1$와 $CDE-r_2$은 반드시 $k$로 나눠떨어질 것이기 때문에 나눠 떨어지는 부분을 제거해 수의 크기를 줄인 것이다. 이것은 $ABCDE$를 어떻게 분리하든 항상 성립한다. 예를들어 $202420$를 $17$로 나눈 나머지는 $1$이다. $24$를 $17$로 나눈 나머지는 $7$이다. 따라서 $20242024$를 $17$로 나눈 나머지는 $107$을 $17$로 나눈 나머지와 같다.

이 방법을 사용해 순열 전체를 저장하지 않고 나머지만 저장하더라도 그 나머지에 수를 그대로 이어붙여 나머지를 연산할 수 있다. 지금까지의 풀이를 그림으로 그려보면 아래와 같다. 사용한 수와 이전 순열을 $k$로 나눈 나머지 2가지만 알 수 있다면 최적값(나눠 떨어지는 순열의 개수)은 고정된다. 즉, 2번 이상 계산할 필요가 없다. 사용한 수를 비트 마스크로 나타내고 그 순열을 $k$로 나눈 값을 이용해 부분 문제로 분할하고 점화식을 세울 수 있다.

점화식

$$\{\begin{array}{l}{n}_{i,j}=\text{j의 사용 상태로 i의 나머지일 때 만들 수 있는 나눠 떨어지는 순열 수}\\ a_i=\text{i번째 수}\\ k=\text{나누는 수}\end{array}$$ $$n_{i,j}=\sum _{p=1}^n(n_{i\times 10^{\lfloor {\log }_{10}(b)\rfloor +1}+a_p\mathrm{mod}k),j\oplus 2^{p-1}})$$

$i\times 10^{\lfloor {\log }_{10}(b)\rfloor +1}+a_p$ 때문에 복잡해보이지만 수 이어붙이는걸 수식으로 표현한 것이니 $\{i\}\{a_p\}$처럼 문자열 더하기를 생각하면 된다. 기저 사례는 모든 수를 다 사용했을 경우이고, 이 때 나머지가 0이라면 한가지 수를 찾은 것이니 1, 0이 아니라면 못 찾은 것이니 0을 반환한다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
using ull = long long;
int n; int k;
vector<vector<ull>> dp;
vector<vector<int>> rt;
vector<string> arr;
int mod(string p) { // 최대 52자리 수를 나누는 함수
	int c = 0;
	for (int i = 0; i < p.size(); i++) {
		c = (c * 10 + p[i] - 48) % k;
	}
	return c;
}
ull r(int c, int st) {// c = 현재 순열의 나머지, st = 사용 상태
	if (st == (1 << n) - 1) return c == 0 ? 1 : 0; // 모든 수를 다 사용했을 때 나머지가 0이면 이 순열은 나눠떨어지는 순열임
	if (dp[c][st] != -1) return dp[c][st];
	ull sum = 0;
	for (int i = 1; i <= n; i++) {
		if ((st & (1 << (i - 1))) != 0) continue;
		if (rt[c][i] == -1) rt[c][i] = mod(to_string(c) + arr[i]); // 현재 순열의 나머지 계산
		sum += r(rt[c][i], st | (1 << (i - 1))); // 현재 순열에 수 하나를 추가한 순열에 대한 결과값 계산
	}
	return dp[c][st] = sum;
}
ull gcd(ull a, ull b) { // 유클리드 호제법
	while (b > 0) {
		ull t = a % b;
		a = b;
		b = t;
	}
	return a;
}
ull f(int p) { // 팩토리얼
	ull ret = 1;
	for (int i = 2; i <= p; i++) {
		ret *= i;
	}
	return ret;
}
int main()
{
	cin >> n; arr = vector<string>(n + 1); 
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	cin >> k;
	dp = vector<vector<ull>>(k, vector<ull>(1 << n, -1));
	rt = vector<vector<int>>(k, vector<int>(n + 1, -1));
	ull res = r(0, 0);// 나눠 떨어지는 순열 수 계산
	if (res == 0) {
		cout << "0/1"; return 0;
	}
	ull mom = f(n);
	if (res == mom) {
		cout << "1/1"; return 0;
	}
	ull g = gcd(res, mom);
	cout << res / g << "/" << mom / g;
	return 0;
}

발상에서 나머지를 인자로 생각하는 직관이 필요하기 때문에 쉽지 않은 문제다.