백준 10830 행렬 제곱 C++

 

간단한 해설

 

A의 B제곱은 분할정복으로 다음과 같은 공식을 사용할 수 있다.

A^B=A^(B/2)*A^(B/2) (B is even)

A^B=A^((B-1)/2)*A^((B-1)/2)*A (B is odd)

 

여기서 B에 해당되는 값들을 잘 생각해보면 1, 2, 2^2, 2^3... 이런식으로 분할할 수 있다.

 

만약에 B가 5라고 생각해보자 그러면 B=2^2+1이라고 생각할 수 있다.

만약, B가 21이라고 생각하면 B=2^4+2^2+1이다.

 

그러면 A의 2제곱n지수들을 메모이제이션하고, B를 비트마스킹해서 그 값들을 곱하는 방식으로 사용하면 된다.

 

B의 최대치가 100000000000이니까 B=100000000000일때를 생각해보자.

 

B를 이진법으로 변환했을 때, 0000000000000000000000000001011101001000011101101110100000000000이 나온다.

그러므로, B&(1<<exponent)의 값이 B&(1<<exponent)일 경우(1이 나오는경우)에만 메모이제이션한 값을 사용하는거다.

 

다시 간단히 설명하자면 B가 21일 경우 memoi[4] x memoi[2] x memoi[0]이다.(memoi를 A의 2^n진법의 메모이제이션 배열이라 정의)

 

 

이제  B=100000000000일 때로 돌아가보자.

0000000000000000000000000001011101001000011101101110100000000000이니까

36 34 33 32 30 27 22 21 20 18 17 15 14 13 11일 때(제일 오른쪽이 0) 비트의 값이 1이다.

그러므로 A^100000000000은 A^(2^36+2^34+2^33+2^32+2^30+2^27+2^22+2^21+2^20+2^18+2^17+2^15+2^14+2^13+2^11)이다.

이는 (A^(2^36)) x (A^(2^34)) x (A^(2^33))...인 값이다.

 

그러므로 memoi[36] x memoi[34] x memoi[33]...이다.

 

이제 행렬 곱셈 계산만 잘 구현하면 끝이다. 

 

물론, 행렬 계산의 특성상, 초기값은 전부 0이나 1로 초기화된 값이 아닌 단위 행렬이어야한다.

 

 

 

참고로, 값을 구하는 과정에서 나머지연산은 단순해보이지만 사실 모듈러 연산의 성질을 알아야한다.

 

 

algorithm/페르마의_소정리 at main · ash9river/algorithm

 

답

 

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
vector<vector<ll>> v;
vector<vector<vector<ll>>> memoi;
ll n,b;
vector<vector<ll>> makeCalc(vector<vector<ll>> one,vector<vector<ll>> two){
	vector<vector<ll>> sum(n,vector<ll>(n,0));
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			for(int k=0;k<n;++k){
				sum[i][j]+=one[i][k]*two[k][j];
				sum[i][j]%=1000;
			}
		}
	}
	return sum;
}

vector<vector<ll>> calc(ll b){
	vector<vector<ll>> ret(n,vector<ll>(n,0));
	int ptr=0;
	for(int i=0;i<n;++i){
		ret[i][ptr]=1;
		++ptr;
	}
	for(ll i=63;i>=0;--i){
		if(b&((ll)1<<i)){
			ret=makeCalc(ret,memoi[i]);
		}
	}
	return ret;
} 

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cin>>n>>b;
	v.resize(n,vector<ll>(n,0));
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			cin>>v[i][j];
		}
	}
	int ptr=0;
	for(ll i=63;i>=0;--i){
		if(b&((ll)1<<i)){
			ptr=i+1;
			break;
		}
	}
	memoi.resize(ptr+1,vector<vector<ll>>(n,vector<ll>(n,98764321)));
 	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			memoi[0][i][j]=v[i][j];
		}
	}
	for(int k=1;k<ptr;++k){
		memoi[k]=makeCalc(memoi[k-1],memoi[k-1]);
	}
	vector<vector<ll>> ans=calc(b);
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			cout<<ans[i][j]<<" ";
		}
		cout<<"\n";
	}
}