12850번: 본대 산책2 - 분할 정복(행렬)

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

12850번: 본대 산책2

 

m[i][j] : 시간 i에 건물 j에 도달할 경우의 수라 한다면

m[i][0] = m[i-1][1] * 1 + m[i-1][2] * 1

m[i][0] = m[i-1][0] * 1 + m[i-1][2] * 1 + m[i-1][3] * 1

m[i][0] = m[i-1][0] * 1 + m[i-1][1] * 1 + m[i-1][3] * 1 + m[i-1][4] * 1

m[i][0] = m[i-1][1] * 1 + m[i-1][2] * 1 + m[i-1][4] * 1 + m[i-1][5] * 1

...

이는 행렬을 이용한 거듭제곱으로 나타낼 수 있다.

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <string>
#include <iomanip>
#define mod 1000000007
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

ll matrix[8][8] =
{
	{0, 1, 1, 0, 0, 0, 0, 0},
	{1, 0, 1, 1, 0, 0, 0, 0},
	{1, 1, 0, 1, 1, 0, 0, 0},
	{0, 1, 1, 0, 1, 1, 0, 0},
	{0, 0, 1, 1, 0, 1, 1, 0},
	{0, 0, 0, 1, 1, 0, 0, 1},
	{0, 0, 0, 0, 1, 0, 0, 1},
	{0, 0, 0, 0, 0, 1, 1, 0},
}; //해당 행렬을 N번 곱하고 {1, 0, 0, 0, 0, 0, 0, 0}과 곱하면 답이다.
ll M[8][8];

void solve(int D)
{
	if (D == 1)
	{
		for (int i{ 0 }; i <= 7; i++)
		{
			for (int j{ 0 }; j <= 7; j++)
			{
				M[i][j] = matrix[i][j];
			}
		}
		return;
	}

	solve(D / 2);

	ll temp[8][8] = {};

	if (D % 2 == 0)
	{
		for (int i{ 0 }; i <= 7; i++)
		{
			for (int j{ 0 }; j <= 7; j++)
			{
				for (int x{ 0 }; x <= 7; x++)
				{
					temp[i][j] += ((M[i][x] % mod) * (M[x][j] % mod)) % mod;
					temp[i][j] %= mod;
				}
			}
		}
	}
	else
	{
		ll t[8][8] = {};
		for (int i{ 0 }; i <= 7; i++)
		{
			for (int j{ 0 }; j <= 7; j++)
			{
				for (int x{ 0 }; x <= 7; x++)
				{
					t[i][j] += ((M[i][x] % mod) * (M[x][j] % mod)) % mod;
					t[i][j] %= mod;
				}
			}
		}
		for (int i{ 0 }; i <= 7; i++)
		{
			for (int j{ 0 }; j <= 7; j++)
			{
				for (int x{ 0 }; x <= 7; x++)
				{
					temp[i][j] += ((t[i][x] % mod) * (matrix[x][j] % mod)) % mod;
					temp[i][j] %= mod;
				}
			}
		}
	}

	for (int i{ 0 }; i <= 7; i++)
	{
		for (int j{ 0 }; j <= 7; j++)
		{
			M[i][j] = temp[i][j];
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int D; cin >> D;
	solve(D);
	cout << M[0][0];
}