import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String[] arr = new String[n]; int totalLen = 0; for (int i = 0; i < n; i++) { arr[i] = br.readLine(); totalLen += arr[i].length(); } int k = Integer.parseInt(br.readLine()); long dp[][] = new long[1 << n][k]; int mod10[] = new int[totalLen]; mod10[0] = 1; for (int i = 1; i < totalLen; i++) { mod10[i] = (mod10[i - 1] * 10) % k; } int mod[] = new int[n]; // 나머지 구하기 for (int i = 0; i < n; i++) { int start = 0; int end = Math.min(arr[i].length(), 10); while (start < end) { String little = arr[i].substring(start, end); long littleNum = Long.parseLong(little); littleNum %= k; mod[i] += (littleNum * mod10[arr[i].length() - end]) % k; start = end; end = Math.min(arr[i].length(), start + 10); } mod[i] %= k; dp[1 << i][mod[i]]++; } // for (int i = 0; i < n; i++) { // System.out.println(mod[i] + " "); // } int len[] = new int[1 << n]; for (int i = 1; i < 1 << n; i++) { for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) { len[i] += arr[j].length(); } } } for (int o = 1; o < n; o++) { for (int j = 1; j < 1 << n; j++) { for (int i = 0; i < n; i++) { if (Integer.bitCount(j) != o || (j & (1 << i)) != 0) continue; for (int l = 0; l < k; l++) { if (dp[j][l] != 0) { int newMod = l + (mod10[len[j]] * mod[i]) % k; newMod %= k; dp[j | (1 << i)][newMod] += dp[j][l]; } } } } } long total = 1; for (int i = 2; i <= n; i++) { total *= i; } long div = gcd(total, dp[(1 << n) - 1][0]); long ans = (int) (dp[(1 << n) - 1][0]/div); total /= div; if (dp[(1 << n) - 1][0] == 0) total = 1; System.out.println(ans + "/" + total); } static long gcd(long a, long b) { if (b == 0) return a; return gcd(b, a % b); } }

제출 #154513

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: