백준 : 1086 JAVA

https://www.acmicpc.net/problem/1086

1086번: 박성원

비트마스크, 메모이제이션, GCD 가 사용된다.

TSP처럼 현재의 상태가 A 일때 방문한노드가 falg(000000000) 일때 값은 얼마인가 하고 물어볼수가 있다.

주의 할점은 숫자의 길이가 50이기때문에 char 형으로 문자를 받고 앞에서부터 나머지 연산을하면서 나머지를 구해야한다.

ex) 5221 에 나머지 17을 구하기 위해선 5221%17 이 아니라 앞에서부터 
5%17 = 5 -> 두번째 문자열로 이월
52%17 = 1 -> 세번째 문자열로 이월
12 %17 = 12 -> 네번째 문자열로 이월
121 %17 = 0 -> 따라서 나머지는 0이다.

일단 길이가 긴 숫자에대해서 나머지를 구할수가 있다.  문제에서는 각각의 문자를 나눈다고했다.
여기서도 지금의 나머지연산을 수행할수가 있다.

현재 방문한 노드가 없는경우 falg = 0 인경우에는 0~N-1 노드들을 가장 문자 맨앞에 놔둘수가 있다.
각각의 경우를 K로 나눈 나머지가 A라면 이월할 A값과 현재 flag를 갱신한다음 념겨줄수가 있다.

이렇게되면 모든 노드를 방문하지안하도 메모이제이션으로 나누어떨어지는 숫자를 빠르게 탐색할수가있다.

package day0314;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class B1086 {
    static int N;
    static int K;
    static char[][] arr;
    static long p;
    static long q;
 
    static long GCD(long a, long b) {
        if (a > b) {
            long tmp = a;
            a = b;
            b = tmp;
        }
 
        while (a % b != 0) {
            long tmp = a % b;
            a = b;
            b = tmp;
        }
        return b;
    }
 
    static long fibo[];
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        N = Integer.parseInt(br.readLine());
        arr = new char[N][];
        for (int i = 0; i < N; i++) {
            arr[i] = br.readLine().toCharArray();
        }
        K = Integer.parseInt(br.readLine());
 
        fibo = new long[N + 1];
        fibo[1] = 1L;
        for (int i = 2; i <= N; i++) {
            fibo[i] = (long)i * fibo[i - 1];
        }
        dp = new long[K][1 << N];
        dpMod = new int[K][N];
        for (int k = 0; k < K; k++) {
            Arrays.fill(dp[k], -1);
            Arrays.fill(dpMod[k], -1);
        }
        
        p = memoi(0, 0, 0);
        q = fibo[N];
        if (p == 0) {
            q = 1;
        } else {
            long gcd = GCD(p, q);
            p /= gcd;
            q /= gcd;
        }
 
        System.out.println(p + "/" + q);
    }
    
    static int dpMod[][];
    
    public static int getMod(int mod,int n) {
        if
        (dpMod[mod][n]!=-1) {
            return dpMod[mod][n];
        }
        int cur = mod;
        for (int j = 0; j < arr[n].length; j++) {
            cur = cur*10;
            cur = (cur +arr[n][j] - '0')% K;
        }
        
        return dpMod[mod][n] =cur; 
    }
    
    public static long memoi(int mod, int cnt, int flag) {
        if (dp[mod][flag] != -1) {
            return dp[mod][flag];
        }
        if (cnt == N) {
            return dp[mod][flag] = mod == 0 ? 1L : 0;
        }
        
        long sum = 0;
        for (int i = 0; i < N; i++) {
            if ((flag & (1 << i)) == (1 << i))
                continue;
            
            sum += memoi(getMod(mod, i),cnt+1,flag|(1<<i));
        }
        
        return dp[mod][flag] = sum;
    }
 
    static long dp[][];
}