제출 #833425

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
833425		rahulverma	아름다운 순열 (IZhO12_beauty)	Java	0 / 100	3032 ms	224688 KiB

beauty

import java.util.*;
import java.io.*;

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);
                }
            }
        }
        if(last != -1)dp[(int) mask][last] = an;
        return an;
    }

    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int i;
        long ans = 0;

        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (i = 0; i < n; i++) {
            long p = Integer.parseInt(st.nextToken());
            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, -1);
        PrintWriter pw = new PrintWriter(System.out);
        pw.println(ans);
        pw.close();
    }
    public static long pow(int i) {
    	long ans = 1;
    	while(i > 0) {
    		ans *= 2;
    		i--;
    	}
    	return ans;
    }
}

• Subtask 1: 0 / 100