인접행렬 분할거듭제곱

vector<vector<ll>> multiply(const vector<vector<ll>>& a, const vector<vector<ll>>& b) 
{
	vector<vector<ll>> ret(10, vector<ll>(10));

	for (int i = 1; i <= 8; i++) 
	{
		for (int j = 1; j <= 8; j++) 
		{
			ll elem = 0;
			for (int k = 1; k <= 8; k++) 
			{
				elem += (a[i][k] * b[k][j]) % MOD;
			}
			ret[i][j] = elem % MOD;
		}
	}
	return ret;
}

while (true)
{
    if (D == 0)
        break;

    if (D % 2 == 1)
    {
        cache = multiply(cache, graph);
        D -= 1;
    }
    graph = multiply(graph, graph);
    D /= 2;
}

https://blog.naver.com/PostView.naver?blogId=gt7461&logNo=110151975370&redirect=Dlog&widgetTypeCall=true&topReferer=https%3A%2F%2Fstack07142.tistory.com%2F119&directAccess=false 

인접행렬과 인접행렬의 거듭제곱

엄청 잘만드신 템플릿

https://kth990303.tistory.com/183