백준 박성원(1086)

박성원

랜선 자르기에서 오영식에서 도움을 요청했던 박성원이 풀지 못한 문제입니다.

1. 힌트

1) 맞출 확률은 합친 수가 정수 $K$로 나누어 지는 순열의 개수 / 만들 수 있는 순열의 개수($N!$)이다.

2) $K$가 매우 작아서 DP를 적용할 수 있다.

3) 이미 순열에 사용한 수들을 알 수 있으면 이번에 사용하게 되는 수가 몇번째 자리에 붙을지 알 수 있음.

2. 접근

1) 내가 문제를 푸는 과정을 수식화할 수 있을까?

박성원은 아무 순열이나 정답이라고 할 것이고, 수열의 원소는 모두 서로 다르므로, 정답을 맞출 확률은

$\displaystyle\frac{\scriptstyle{조건을\ 만족하는\ 순열의 수}}{N!}$
기약분수로 나타내려면 분모 분자의 최대 공약수로 분모 분자를 각각 나눠줘야 한다. 경우의 수를 구하는 문제는 십중팔구 DP로 해결 가능하므로 이 문제도 가능한지 생각해보자.

2) 문제를 분해할 수 있을까?

재귀함수를 통해 문제를 해결하는 함수를 만들고 이 함수에 메모이제이션을 적용해서 DP함수를 정의해보자, 직관적으로 우리는 매번의 단계를 $N$개의 순열중에서 하나를 고르는 선택을 할 수 있다. 똑같은 원소를 두 번 고르지 않게 하기 위해서는 선택한 순열의 정보를 가지고 있어야 하는데, $N$이 최대 15이므로 비트마스킹을 통해 나타내면 함수의 인자로 사용할 수 있다. 그런데 지금까지 고른 수들을 이어붙인 결과는 너무 커서 인자로 가지고 있을 순 없다. 이어붙인 수를 $K$로 나눈 나머지를 이전 선택에 대한 정보로 유지하면 $K$가 최대 $100$이므로 인자로 사용할 수 있다.

3) 문제를 단순화할 수 없을까?

15
10000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000002
10000000000000000000000000000000000000000000000004
10000000000000000000000000000000000000000000000006
10000000000000000000000000000000000000000000000008
10000000000000000000000000000000000000000000000010
10000000000000000000000000000000000000000000000012
10000000000000000000000000000000000000000000000014
10000000000000000000000000000000000000000000000016
10000000000000000000000000000000000000000000000018
10000000000000000000000000000000000000000000000020
10000000000000000000000000000000000000000000000022
10000000000000000000000000000000000000000000000024
10000000000000000000000000000000000000000000000026
10000000000000000000000000000000000000000000000028
2
->1/1

이와 같은 입력을 생각해보자, 물론 자리수가 저렇게나 크기 때문에 32비트나 64비트 정수 자료형으로 변환할 수는 없다. 이 때, 모듈러 연산의 성질을 이용하면 주어진 원소들을 간단하게 줄일 수 있다.
$(a + b)\ mod\ K\ = ((a \mod\ K) + (b \mod\ K))\ mod\ K$
$(a \times b)\ mod\ K\ = ((a \mod\ K) \times (b \mod\ K))\ mod\ K$
원소들을 이어 붙인 결과는 각각의 원소들에게 적절하게 $10^n$을 곱해준 뒤 더해준 형태이므로,
주어진 원소들을 미리 $K$로 나누어도 답과는 전혀 상관이 없다.
또한 수를 이어 붙이는 과정을 기존의 수의 오른쪽에 붙인다고 가정하자, 예를 들면 $remainder$를 지금까지 이어 붙인 수를 $K$로 나눈 나머지라고 할 때, $remainder = 98$ 에 $99$를 이어 붙인다고 하자, 그렇다면 결과는 $9899$가 될 것이다.
이는 $remainder \times 10^{|S|}\ + S$와 같은 연산이라고 이해할 수 있다. ($|S|$는 원소 $S$의 길이)

3. 구현

public class Main {
	static int N; static int[][] S;// (S[i] % MOD, |S[i]|)
	static long[][] cache;
	static int MOD;
	static int[] D; // 10^i 를 MOD로 나눈 나머지를 저장

	// 사용한 수열이 b고 지금까지 수를 MOD로 나눈 나머지가 remainder일때, N개의 수열을 모두 사용해 붙여서 만든 수가
	// K로 나누어 떨어지는 경우의 수
	static long dp(int b, int remainder) {
		// 모든 수열의 원소를 사용해 붙였으면 나누어 떨어지는지 확인
		if (b == ((1 << N) - 1)) return remainder == 0 ? 1 : 0;
		if (cache[b][remainder] != -1) return cache[b][remainder];
		long sum = 0;
		for (int i = 0; i < N; i++)
			if ((b & (1 << i)) == 0)
				sum += dp(b | (1 << i), ((remainder * D[S[i][1]]) % MOD + S[i][0] % MOD) % MOD);
		return cache[b][remainder] = sum;
	}

	static long gcd(long a, long b) {
		if (b == 0) return a;
		return gcd(b, a % b);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		String[] temp = new String[N];
		for (int i = 0; i < N; i++) temp[i] = br.readLine();
		MOD = Integer.parseInt(br.readLine());
		// D 초기화
		D = new int[50 * 15]; D[0] = 1;
		for (int i = 1; i < D.length; i++) D[i] = (D[i - 1] * 10) % MOD;
		S = new int[N][2];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < temp[i].length(); j++)
				S[i][0] = (S[i][0] + ((temp[i].charAt(temp[i].length() - j - 1) - '0') * D[j]) % MOD) % MOD; 
			S[i][1] = temp[i].length();
		}
		cache = new long[1 << N][MOD];
		for (int i = 0; i < cache.length; i++) Arrays.fill(cache[i], -1);
		// (a / b)를 기약분수로 나타낸다
		long a = dp(0, 0); long b = 1;
		for (int i = 2; i <= N; i++) b *= i;
		long t = gcd(a, b);
		a /= t; b /= t;
		System.out.println(a + "/" + b);
	}

}

1) 시간 복잡도

존재할 수 있는 부분 문제의 개수는 $O(2^N \times K)$이고, 함수 하나의 시간 복잡도는 $O(N)$이므로 시간 복잡도는 $O(2^N \times K \times N)$이 된다.

2) 테스트 케이스

15
10000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000002
10000000000000000000000000000000000000000000000004
10000000000000000000000000000000000000000000000006
10000000000000000000000000000000000000000000000008
10000000000000000000000000000000000000000000000010
10000000000000000000000000000000000000000000000012
10000000000000000000000000000000000000000000000014
10000000000000000000000000000000000000000000000016
10000000000000000000000000000000000000000000000018
10000000000000000000000000000000000000000000000020
10000000000000000000000000000000000000000000000022
10000000000000000000000000000000000000000000000024
10000000000000000000000000000000000000000000000026
10000000000000000000000000000000000000000000000028
2
->1/1

어떤 수가 맨 끝에 오더라도 짝수이기 때문에 확률은 1/1이다.

15
10000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000002
10000000000000000000000000000000000000000000000004
10000000000000000000000000000000000000000000000006
10000000000000000000000000000000000000000000000008
10000000000000000000000000000000000000000000000010
10000000000000000000000000000000000000000000000012
10000000000000000000000000000000000000000000000014
10000000000000000000000000000000000000000000000016
10000000000000000000000000000000000000000000000018
10000000000000000000000000000000000000000000000020
10000000000000000000000000000000000000000000000022
10000000000000000000000000000000000000000000000024
10000000000000000000000000000000000000000000000026
10000000000000000000000000000000000000000000000028
1
->1/1

1로 나누어 떨어지지 않는 자연수는 없다.

3
1
3
5
2
->0/1

어떤 수가 맨 오른쪽에 오더라도 홀수이기 때문에 불가능하다.

3
1
2
12
21
->1/6

맨 끝 두자리가 $21$이라고 해서 무조건 $21$로 나누어 떨어지는 것이 아니다
ex) 1221