[Link] https://www.acmicpc.net/problem/1086
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader br;
static StringBuilder sb = new StringBuilder();
static ArrayList<Integer> expdp;
static int n;
static int k;
static String[] line;
static int[] convert;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
n = toi(br.readLine());
line = new String[n];
convert = new int[n];
Arrays.fill(convert, -1);
int l = 0;
for(int i = 0; i < n; i++) {
line[i] = br.readLine();
l += line[i].length();
}
k = toi(br.readLine());
long[][] dp = new long[k][1 << n];
for(long[] ar: dp) Arrays.fill(ar, -1);
expdp = new ArrayList<>();
expdp.add(1);
long num = dfs(dp, 0, (1 << n) - 1, l);
printProb(num);
}
static int convert(int idx) {
if(convert[idx] != -1) return convert[idx];
int sum = 0;
String s = line[idx];
for(int i = 0; i < s.length(); i++)
sum = (sum * 10 + s.charAt(i) - '0') % k;
return convert[idx] = sum;
}
static long dfs(long[][] dp, int remain, int bitmask, int len) {
if(dp[remain][bitmask] != -1) return dp[remain][bitmask];
if(bitmask == 0) return dp[remain][bitmask] = (remain == 0 ? 1 : 0);
int bit = 1;
long sum = 0;
for(int i = 1; i <= n; i++) {
if((bitmask & bit) == 0) {
bit <<= 1;
continue;
}
int ll = len - line[i - 1].length();
int pair = remain - (convert(i - 1) * tenExp(ll) % k);
if(pair == k) pair = 0;
if(pair < 0) pair += k;
if(dfs(dp, pair, bitmask ^ bit, ll) != -1)
sum += dfs(dp, pair, bitmask ^ bit, ll);
bit <<= 1;
}
return dp[remain][bitmask] = sum;
}
static void printProb(long num) {
if(num == 0) {
print("0/1");
return;
}
long denominator = 1;
for(int i = 2; i <= n; i++) denominator *= i;
long gcd = gcd(num, denominator);
denominator /= gcd;
num /= gcd;
print(num + "/" + denominator);
}
static long gcd(long a, long b) {
long max = Math.max(a, b), min = Math.min(a, b);
while(true) {
long re = max % min;
if(re == 0) break;
max = min;
min = re;
}
return min;
}
static int tenExp(int n) {
if(expdp.size() >= n + 1) return expdp.get(n);
int idx = expdp.size();
int tmp = expdp.get(idx - 1);
while(idx <= n) {
tmp = (tmp * 10) % k;
expdp.add(tmp);
idx++;
}
return tmp;
}
static int toi(String s) { return Integer.parseInt(s); }
static long tol(String s) { return Long.parseLong(s); }
static String[] getLine() throws IOException { return br.readLine().split(" "); }
static int[] getArr() throws IOException { return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); }
static <T> void print(T s) { System.out.print(s); }
static <T> void println(T s) { System.out.println(s); }
}