백준 12850 본대 산책 2

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

12850번: 본대 산책2

N = 10억이므로 시간복잡도가 기존의 O(N)인 알고리즘 또한 먹히지 않는다. (물론 10억 개수의 변수를 메모리 공간에 저장하려고 하면 메모리 초과가 날 것이다.)

Vertex 사이의 거리가 모두 같다는 점을 이용해서 그래프의 인접행렬의 거듭제곱을 하면 O(8*8*logN)시간에 경우의 수를 구할 수 있다.

package 백준;

import java.util.Scanner;

public class 본대산책2 {
	static long map[][];

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		map = new long[8][8];
		map[0][1] = 1;
		map[0][2] = 1;
		map[1][0] = 1;
		map[1][2] = 1;
		map[1][3] = 1;
		map[2][0] = 1;
		map[2][1] = 1;
		map[2][3] = 1;
		map[2][5] = 1;
		map[3][1] = 1;
		map[3][2] = 1;
		map[3][4] = 1;
		map[3][5] = 1;
		map[4][3] = 1;
		map[4][5] = 1;
		map[4][6] = 1;
		map[5][2] = 1;
		map[5][3] = 1;
		map[5][4] = 1;
		map[5][7] = 1;
		map[6][4] = 1;
		map[6][7] = 1;
		map[7][5] = 1;
		map[7][6] = 1;
		long c[][] = new long[8][8];
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				c[i][j] = map[i][j];
			}
		}


		c = mypow(c, N);
		System.out.println(c[0][0]);
	}

	static int M = 1000000007;

	private static long[][] mult(long[][] c1, long[][] c2) {
		long res[][] = new long[8][8];
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				for (int k = 0; k < 8; k++)
					res[i][j] = (res[i][j] + c1[i][k] * c2[k][j]) % M;
			}
		}
		return res;
	}

	private static long[][] mypow(long[][] c, long N) {
		// System.out.println("N= "+ N);
		if (N == 1)
			return c;
		else {
			if (N % 2 == 1) {
				long res[][] = new long[8][8];
				res = mult(c, c);
				return mult(c, mypow(res, N / 2));

			} else {
				long res[][] = new long[8][8];

				res = mult(c, c);
				return mypow(res, N / 2);
			}
		}

	}

	private static void printMat(long[][] res) {
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				System.out.print(res[i][j] + " ");
			}
			System.out.println();
		}
	}

}