import java.util.*;
public class beauty {
static long[] a = new long[100];
static long[] b = new long[100];
static long[][] dp = new long[1 << 20][23];
static int n;
static long rec(long mask, int last) {
if (mask == (pow(n) - 1)) return 1;
if (last != -1 && dp[(int) mask][last] != -1) return dp[(int) mask][last];
long an = 0;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) == 0) {
if (last == -1 || a[(int) last] == a[i] || b[(int) last] == b[i]) {
an += rec(mask | pow(i), i);
}
}
}
return dp[(int) mask][last] = an;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int i;
long ans = 0;
n = scanner.nextInt();
for (i = 0; i < n; i++) {
long p = scanner.nextLong();
a[i] = Long.bitCount(p);
long p1 = p;
while (p1 > 0) {
if (p1 % 3 == 1) b[i]++;
p1 /= 3;
}
}
for (i = 0; i < pow(20); i++) {
Arrays.fill(dp[i], -1);
}
ans += rec(0, 0);
System.out.println(ans);
}
public static long pow(int i) {
long ans = 1;
while(i > 0) {
ans *= 2;
i--;
}
return ans;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
379 ms |
224720 KB |
Output is correct |
2 |
Correct |
374 ms |
223696 KB |
Output is correct |
3 |
Correct |
358 ms |
223732 KB |
Output is correct |
4 |
Correct |
369 ms |
223872 KB |
Output is correct |
5 |
Incorrect |
372 ms |
223684 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |