랜선 자르기에서 오영식에서 도움을 요청했던 박성원이 풀지 못한 문제입니다.
박성원은 아무 순열이나 정답이라고 할 것이고, 수열의 원소는 모두 서로 다르므로, 정답을 맞출 확률은
기약분수로 나타내려면 분모 분자의 최대 공약수로 분모 분자를 각각 나눠줘야 한다. 경우의 수를 구하는 문제는 십중팔구 DP로 해결 가능하므로 이 문제도 가능한지 생각해보자.
재귀함수를 통해 문제를 해결하는 함수를 만들고 이 함수에 메모이제이션을 적용해서 DP함수를 정의해보자, 직관적으로 우리는 매번의 단계를 개의 순열중에서 하나를 고르는 선택을 할 수 있다. 똑같은 원소를 두 번 고르지 않게 하기 위해서는 선택한 순열의 정보를 가지고 있어야 하는데, 이 최대 15이므로 비트마스킹을 통해 나타내면 함수의 인자로 사용할 수 있다. 그런데 지금까지 고른 수들을 이어붙인 결과는 너무 커서 인자로 가지고 있을 순 없다. 이어붙인 수를 로 나눈 나머지를 이전 선택에 대한 정보로 유지하면 가 최대 이므로 인자로 사용할 수 있다.
15
10000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000002
10000000000000000000000000000000000000000000000004
10000000000000000000000000000000000000000000000006
10000000000000000000000000000000000000000000000008
10000000000000000000000000000000000000000000000010
10000000000000000000000000000000000000000000000012
10000000000000000000000000000000000000000000000014
10000000000000000000000000000000000000000000000016
10000000000000000000000000000000000000000000000018
10000000000000000000000000000000000000000000000020
10000000000000000000000000000000000000000000000022
10000000000000000000000000000000000000000000000024
10000000000000000000000000000000000000000000000026
10000000000000000000000000000000000000000000000028
2
->1/1
이와 같은 입력을 생각해보자, 물론 자리수가 저렇게나 크기 때문에 32비트나 64비트 정수 자료형으로 변환할 수는 없다. 이 때, 모듈러 연산의 성질을 이용하면 주어진 원소들을 간단하게 줄일 수 있다.
원소들을 이어 붙인 결과는 각각의 원소들에게 적절하게 을 곱해준 뒤 더해준 형태이므로,
주어진 원소들을 미리 로 나누어도 답과는 전혀 상관이 없다.
또한 수를 이어 붙이는 과정을 기존의 수의 오른쪽에 붙인다고 가정하자, 예를 들면 를 지금까지 이어 붙인 수를 로 나눈 나머지라고 할 때, 에 를 이어 붙인다고 하자, 그렇다면 결과는 가 될 것이다.
이는 와 같은 연산이라고 이해할 수 있다. (는 원소 의 길이)
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);
}
}
존재할 수 있는 부분 문제의 개수는 이고, 함수 하나의 시간 복잡도는 이므로 시간 복잡도는 이 된다.
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
맨 끝 두자리가 이라고 해서 무조건 로 나누어 떨어지는 것이 아니다
ex) 1221