| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 833407 | rahulverma | 아름다운 순열 (IZhO12_beauty) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
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, long last) {
if (mask == ((1 << 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 | (1 << 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 < (1 << 20); i++) {
Arrays.fill(dp[i], -1);
}
ans += rec(0, -1);
System.out.println(ans);
}
}