15936번 Hypercube
문제
설계
앗 영어문제
아니 진짜 뭔 이딴문제만 걸리냐?
시간제한이 0.2초인데 이거 자바로 되나 싶었는데 푼 사람 목록보니 파이썬도 있다.
알고리즘 잘 짜면 자바도 되겠지 뭐…
입력으로 N, M, K를 준다.
- N: N차원 하이퍼 큐브
- M: 노드 번호
- K: 경로 길이
하이퍼 큐브가 머에여???
초입방체 - 나무위키
2^N개의 노드를 가지며 x에서 y로 가려면 x < y 이고 xor 연산 시 2^p가 되어야 한다.(비트가 하나 다르다.)
라고 문제에서 말해줌.
문제가 요구하는 건 3가지인데
a. M 번 노드로 향하는 간선이 시작하는 노드 번호의 최댓값
b. M 번 노드에서 시작하는 간선이 향하는 노드 번호의 최소값
c. 찾을 수 있는 K-길이의(K개의 간선을 포함하는) 경로의 개수. 100003 나머지 연산.
허허 이게 국어가 맞나
딱 봐도 하이퍼 큐브를 구현하면 제한 시간에 걸려 터진다.
더 좋은 수학실력이 필요하다는 뜻임…
구글링으로 수학 고수들을 통해 문제 해결 공식을 얻은 다음 구현은 내가 하는 쪽으로 한다.
나 혼자서는 풀 수 없음…
구현
1. 입력 받기
Scanner 사용하면 터질 것 같으니 버퍼로 입력 받는다.
public static void main(String[] args) {
try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
}catch(IOException e) {
e.printStackTrace();
}
}
2. a번 문제
a. M 번 노드로 향하는 간선이 시작하는 노드 번호의 최댓값
일단 M번 노드로 향하는 거니 M보다 작은 노드가 범인이다.
어차피 모든 노드는 작은 수에서 큰 수로 이어지니 M번 노드보다 하나 작은, xor 연산에서 비트 하나 다른 놈을 찾아야한다.
반복문으로 1인 비트를 반전시켜서 비교한다.
// a번: 이진수 M의 1을 반전시킨 수 중 최대값
// 최대값 저장용
int a = Integer.MIN_VALUE;
// 0번째 비트부터 올라감, 100,000,000는 27비트
for (int i = 0 ; i < 27 ; i++){
// M의 i번째 비트가 1인 경우
// == 1 할 경우 0번째 비트만 체크해서 오류 발생
//if ((M & (1 << i)) == 1) {
if ((M & (1 << i)) != 0) {
int m = M ^ (1 << i); // 반전
if (m < M && m > a) {
a = m;
}
}
}
3. b번 문제
a번이랑 비슷한데, 각 비트를 반전시켜서 최소값을 찾으면 된다.
// b번: M의 비트 하나를 반전시킨 수 중 M보다 큰 최소값 찾기
// 최소값 저장용
int b = Integer.MAX_VALUE;
for (int i = 0 ; i < 27 ; i++){
// i번째 비트를 반전시킨 숫자
int m = M ^ (1 << i);
if (m > M && b > m) {
b = m;
}
}
4. c번 문제
해밍 무게 변화에 따른 경로 수를 구하는 것.
전이 관계를 행렬 형태로 표현한 뒤, 행렬 거듭제곱을 통해 빠르게 K 단계를 계산한다.
즉, 전체 시스템을 크기 N+1의 전이 행렬로 보고, dpK = T^K * dp₀ 형태로 계산하는 것이다!
엄….
좋아 완벽하게 이해했어!!
일단 시간복잡도가 O(NK)면 절대 통과하지 못한다.
O(N log K)로 바꾸면 통과가 가능하다.
// c번: 공식계산
doFactorials(N);
// 초기 상태 dp0: 해밍 무게 w를 가진 노드 수 = C(N, w)
int[] dp = new int[N + 1];
for (int w = 0; w <= N; w++) {
dp[w] = C(N, w);
}
// 전이 행렬 생성 (희소 형태로)
List<List<Pair>> T = new ArrayList<>();
for (int i = 0; i <= N; i++) {
T.add(new ArrayList<>());
}
for (int w = 0; w < N; w++) {
// 해밍 무게가 w인 노드에서 w+1로 갈 수 있는 경우만 존재
T.get(w + 1).add(new Pair(w, N - w));
}
// 희소 행렬 거듭제곱을 dp에 적용
int[] dpK = sparseMatPowApply(T, dp, K, N + 1);
// 모든 해밍 무게에서 끝나는 경로 수 합
int c = 0;
for (int w = 0; w <= N; w++) {
c = (c + dpK[w]) % 100003;
}
// ... 중략 ...
// 거듭제곱 계산
public static int P(int b, int e) {
int r = 1;
while (e > 0) {
if ((e & 1) == 1) {
// 거듭제곱 계산
r = (int)((1L * r * b) % 100003);
}
b = (int)((1L * b * b) % 100003);
e >>= 1;
}
return r;
}
// 팩토리얼 및 역팩토리얼 계산 (페르마 소정리 활용)
public static void doFactorials(int N) {
factorial = new int[N + 1];
invFactorial = new int[N + 1];
factorial[0] = 1;
for (int i = 1; i <= N; i++) {
// 팩토리얼 계산
factorial[i] = (int)((1L * factorial[i - 1] * i) % 100003);
}
// 역팩토리얼 (페르마의 소정리)
invFactorial[N] = P(factorial[N], 100003 - 2);
for (int i = N - 1; i >= 0; i--) {
// 역팩토리얼 누적 계산
invFactorial[i] = (int)((1L * invFactorial[i + 1] * (i + 1)) % 100003);
}
}
// 이항계수 계산
public static int C(int N, int w) {
if (w < 0 || w > N) {
return 0;
}
// C(n, r) 계산
return (int)(1L * factorial[N] * invFactorial[w] % 100003 * invFactorial[N - w] % 100003);
}
// 희소행렬 형태: 각 행마다 (열, 값) 쌍 저장
public static class Pair {
int col, val;
Pair(int col, int val) {
this.col = col;
this.val = val;
}
}
// 희소 행렬 곱셈
public static int[] sparseMatVecMul(List<List<Pair>> mat, int[] vec, int size) {
int[] res = new int[size];
for (int i = 0; i < size; i++) {
for (Pair p : mat.get(i)) {
res[i] = (int)((res[i] + 1L * p.val * vec[p.col]) % 100003);
}
}
return res;
}
// 희소 행렬 거듭제곱과 곱셈
public static int[] sparseMatPowApply(List<List<Pair>> T, int[] vec, int exp, int size) {
// 초기 단위 행렬 적용: vec는 dp로 시작
while (exp > 0) {
if ((exp & 1) == 1) {
vec = sparseMatVecMul(T, vec, size);
}
// T = T * T (희소 곱)
List<List<Pair>> newT = new ArrayList<>();
for (int i = 0; i < size; i++) {
newT.add(new ArrayList<>());
}
for (int i = 0; i < size; i++) {
for (Pair kv1 : T.get(i)) {
for (Pair kv2 : T.get(kv1.col)) {
int val = (int)((1L * kv1.val * kv2.val) % 100003);
newT.get(i).add(new Pair(kv2.col, val));
}
}
}
// 중복 열 통합
for (int i = 0; i < size; i++) {
if (newT.get(i).isEmpty()) continue;
List<Pair> row = newT.get(i);
row.sort(Comparator.comparingInt(p -> p.col));
List<Pair> compressed = new ArrayList<>();
int lastCol = -1, sum = 0;
for (Pair p : row) {
if (p.col == lastCol) {
sum = (sum + p.val) % 100003;
} else {
if (lastCol != -1) compressed.add(new Pair(lastCol, sum));
lastCol = p.col;
sum = p.val;
}
}
if (lastCol != -1) compressed.add(new Pair(lastCol, sum));
newT.set(i, compressed);
}
T = newT;
exp >>= 1;
}
return vec;
}
채점
반성
c번에서 계속 시간초과 나길래 C++로 돌려보고 로직 문제란걸 깨닫고 구글링했다.
내 힘으로 풀 수 있는 문제가 아니었다.
수학공부한 셈 쳐야지 뭐.
코드 확인