헥사코인 잼

Code Jam 팀의 첫 암호화폐인 잼코인은 인기를 얻지 못했다. 올해는 16진법을 사용한다는 데서 이름을 딴 헥사코인으로 다시 도전한다. D자리 헥사코인을 "채굴"하려면, 필요할 경우 앞에 오는 영을 포함하여 정확히 D개의 16진법 자릿수를 사용하는 정수들을 다뤄야 한다. 각 값은 양 끝을 포함하여 0 이상 $16^{D}$ - 1 이하의 정수를 나타낸다. 일반적인 방식대로, 16진법의 숫자는 0부터 9까지의 수와 대문자 A부터 F까지로 나타낸다. 예를 들어 D=3일 때 F2B, 0C8, 000은 유효한 값이며, 각각 10진법 값 3883, 200, 0에 해당한다. 반면 D=3일 때 1234, DF, C0DE, JAM은 유효한 값이 아니다.

D자리 16진법 값들을 덧셈할 때는 넘치는 모든 자릿수를 버린다. 즉, 덧셈은 $16^{D}$을 법으로 하여 수행한다. 예를 들어 F2B + 0C8 = FF3이고(이는 10진법으로 4083이다), F2B + F2B = E56이다(합의 결과가 7766이고 이를 $16^{3}$로 나눈 나머지가 3670이므로, 10진법으로 3670이다).

D자리 헥사코인을 "채굴"하려면 컴퓨터는 다음 단계를 수행해야 한다.

• N개의 D자리 16진법 값 $L_{1}$, $L_{2}$, ..., $L_{N}$으로 이루어진 목록 L을 선택한다.

• D자리 16진법 값들의 목표 범위, 즉 양 끝을 포함하여 S부터 E까지의 수를 선택한다.

• 16진법 숫자 0부터 F까지의 순열 P를 가능한 16!개의 모든 순열 중에서 균등한 확률로 무작위 선택한다.

• 목록에 있는 모든 수의 모든 자릿수에 P를 적용하여, N개의 D자리 16진법 값으로 이루어진 새 목록 L'을 만든다. 엄밀히 말해, L'의 i번째 원소의 j번째 자릿수는 L의 i번째 원소의 j번째 자릿수에 P를 적용한 결과이다.

• L'에서 원소 한 쌍을 비복원 방식으로, 가능한 모든 선택 중에서 균등한 확률로, 그리고 순열의 선택과 독립적으로 무작위 선택한다.

• 선택한 두 원소의 합을 계산하되, 넘치는 자릿수는 버린다.

마지막 단계에서 계산한 합이 양 끝을 포함하여 S와 E 사이에 있다면 헥사코인을 찾은 것이다! 예를 들어 다음과 같다고 하자.

• $L = [134, 000, FFB, 000, AA9]$.

• S = 85C이고 E = EDF이다.

• 컴퓨터가 우연히 P = (0 → 4, 1 → A, 2 → 2, 3 → 8, 4 → 9, 5 → B, 6 → C, 7 → 7, 8 → F, 9 → 1, A → 0, B → 3, C → 5, D → 6, E → E, F → D)를 선택했다고 하자.

그러면 L에 P를 적용하여 얻은 L'은 $[A89, 444, DD3, 444, 001]$이다. P는 S와 E에는 적용하지 않는다는 점에 유의하라.

선택할 수 있는 값의 쌍은 (5 × 4) / 2 = 10개이고, 각 쌍이 선택될 확률은 1/10이다. 범위 안에 들어가는 합은 A89 + DD3 = 85C, 444 + 444 = 888, A89 + 001 = A8A, DD3 + 001 = DD4, 그리고 A89 + 444 = ECD(두 번)뿐이다.

처음 두 단계는 이미 계산되었으며, 선택된 목록 L과 범위 [S, E]를 알고 있다. 나머지 과정을 수행한 뒤 헥사코인을 찾을 확률은 얼마인가?

제한

시간 제한: 테스트 세트당 90초. 메모리 제한: 1GB. 2 ≤ N ≤ 450. S는 정확히 D개의 문자를 포함한다. S의 각 문자는 16진법 숫자이다. E는 정확히 D개의 문자를 포함한다. E의 각 문자는 16진법 숫자이다. S ≤ E. 모든 i에 대해 $L_{i}$는 정확히 D개의 문자를 포함한다. 모든 i에 대해 $L_{i}$의 각 문자는 16진법 숫자이다.

테스트 세트 1 (공개 판정)

1 ≤ T ≤ 100. 2 ≤ D ≤ 3.

테스트 세트 2 (비공개 판정)

1 ≤ T ≤ 100. 2 ≤ D ≤ 4.

테스트 세트 3 (비공개 판정)

1 ≤ T ≤ 10. 2 ≤ D ≤ 5.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다. 첫 줄에는 두 정수 N과 D가 주어지며, 각각 주어진 목록의 크기와 다룰 자릿수이다. 둘째 줄에는 D자리 16진법 수 S와 E가 주어지며, 각각 목표 범위의 양 끝을 포함하는 하한과 상한이다. 그다음 한 줄에는 목록의 값들을 나타내는 N개의 D자리 16진법 수 $L_{1}$, $L_{2}$, ..., $L_{N}$가 주어진다.

각 테스트 케이스마다 Case #x: y z을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y과 z은 음이 아닌 정수이고, 분수 y/z는 위에서 설명한 조건에서 헥사코인을 찾을 확률을 나타낸다. x, y, z는 모두 10진법이어야 한다. y와 z에 허용되는 값이 여러 개라면, z이 최소가 되도록 선택한다.

예제 케이스 #1에서 목표 범위는 단 하나의 값 10뿐이다. 결과가 0로 끝나므로, 두 마지막 자릿수 0와 F에 배정된 값의 합도 0로 끝나야 한다. P[0]와 P[F]는 서로 다른 값이므로 그 합은 정확히 0일 수 없다. 따라서 P[0] + P[F]는 10이어야 한다(16진법 기준). 이를 만족하는 서로 다른 숫자의 쌍은 7개이다. P[0]와 P[F]가 둘 다 8일 수는 없다. 7개의 모든 쌍은 전체 합이 10이 되게 한다(넘치는 1을 버린 뒤). 따라서 0와 F에 서로 다른 숫자를 배정하여 헥사코인을 얻게 되는 경우는 14개이다. 이 숫자들에 값을 배정하는 방법은 16 × 15개이므로 결과는 14/240 = 7/120이다.

예제 케이스 #2에서는 결과가 정확히 11일 확률을 예제 케이스 #1의 결과에 더해야 한다. 그렇게 되는 유일한 방법은 0와 F에 0와 1를 어느 순서로든 배정하는 것이다. 그 확률은 2/240=1/120이므로, 총확률은 7/120 + 1/120 = 8/120 = 1/15이다.

예제 케이스 #3에서는 컴퓨터가 목록에서 어떤 순열과 수의 쌍을 선택하든, 같은 숫자로 끝나는 두 수를 더하게 된다는 점에 유의하라. 그러면 $16^{3}$을 법으로 취한 뒤에도 결과는 짝수가 된다. 범위 안의 유일한 값은 홀수이므로, 이 경우에는 헥사코인을 채굴할 가능성이 없다. z가 최소가 아니므로 0 2은 올바르지 않은 답의 표현이라는 점에 유의하라.