행렬의 제곱

 

분할 정복, DP 문제에서 N이 아주 크게 주어지는 경우 자주 이용됨

분할 정복을 이용한 거듭제곱에 있는 문제 거의 다 이런 문제일 것 같다.

 

 

struct로 행렬을 구현해 곱셈 연산자 오버로딩. 

15행에 출력 조건과 수의 범위에 따라 MOD연산 등을 추가한다.

당연하지만 이때 음수 MOD연산도 주의하자,, 통수 맞을 수 있음,,

struct Matrix {
	int size;
	vector<vector<long long>> a;
	Matrix() { size = 0; }
	Matrix(int n) {
		size = n;
		a = vector<vector<long long>>(n, vector<long long>(n));
	}
	Matrix operator *(const Matrix& X) {
		Matrix RES(size);
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				for (int k = 0; k < size; k++) {
					RES.a[i][j] += a[i][k] * X.a[k][j];
					//add some operations
				}
			}
		}
		return RES;
	}
};

덧셈이나 뺄셈할 일이 있다면 마찬가지로 오버로딩 해주기

 

 

행렬의 크기가 정해져있고 원소를 이용해 초기화하고 싶다면 아래와 같이 해주면 된다. DP 중에서도 수열 값을 구할 때 주로 이용함. 피보나치 수 3이라던지,, 타일 채우기 2라던지. 11행은 위 코드의 연산에서 size만 바꿔주면 됨

struct Matrix {
	long long a[2][2];
	Matrix() { a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0; }
	Matrix(long long x, long long y, long long z, long long w) {
		a[0][0] = x; a[0][1] = y;
		a[1][0] = z; a[1][1] = w;
	}
	Matrix operator *(const Matrix& X) {
		Matrix RES(0,0,0,0);
		for (int i = 0; i < 2; i++) {
			...
		}
		return RES;
	}
};

엥근데 다시보니 굳이 왜,, (0,0,0,0) 썼지 그냥 해도 되는데? ......?

 

 

제곱은 당연히 재귀로 구현한다.

Matrix pow(Matrix X, int n) {
	if (n == 1) return X;
	Matrix RES = pow(X, n / 2);
	RES = RES * RES;
	if (n % 2) RES = RES * X;
	return RES;
}

 

 

 

까먹지 말자,,

 

DP 중 시리즈 문제가 있다면 마지막은 대개 항상 행렬의 제곱을 이용하는 문제였던 것 같음. 

간간히 나오면 당황 한 번 하고 뭐였지,,, 이러다가 생각이라도 나면 다행인데 와중에 구현하는 법은 또 헷갈리고 그래서 좀 다시 들여다봤다,,

더불어 오버로딩 연습을 좀 더 해야할 듯.. 클래스도 거의 모르고ㅜ 아이고 이래서 어디가서 코딩할 줄 안다고 얘기나 하겠나,,