백준 13430(합 구하기)

www.acmicpc.net/problem/13430

13430번: 합 구하기

행렬의 점화식을 이용한 문제이다. 

 

문제에 행렬의 점화식을 이용해서 풀라 이런 문구는 없어서 풀이방법을 찾아내기 어렵겠지만 아마도 이런 점화식이 주어진 문제를 보면 또 N이 엄청나게 큰 문제를 보면 행렬의 점화식을 떠올릴 수 있을 것 같기도 한 문제였다. 

 

먼저 우리에게는 점화식이 주어진다.

 

S(0,N) = N

S(K,N) = S(K-1, 1) + ... + S(K-1, N) 

 

여기서 내가 짚고 넘어갈 것은 N의 범위가 10억까지이다. 따라서 N은 엄청나게 크고, O(N)의 풀이는 안되고, O(logN)같은 풀이를 찾아야한다는 것이다. 

 

따라서 행렬의 점화식을 이용하면 logN의 풀이가되는것을 생각해내고, 점화식을 세울 준비를 한다. 

 

단순하게 규칙을 찾는다. 라는 생각을 가지고 처음에 접근했었는데 말도 안되게 어려웠다. 어떤 규칙을 찾는지 내가 어떤 꼴의 행렬을 원하는지도 모르는 상황이었기 때문이다. 

 

따라서 우리는 행렬의 점화식이 어떤식으로 세워지는지 생각해야한다. 

 

가장 간단한 피보나치 수열을 한번 보자 

 

피보나치의 기본 점화식은 

 

Fn = Fn-1+Fn-2(n>=2)

Fn = 1 (n=1)

Fn = 1 (n=0)

 

이렇게 된다. 우리가 원하는 것은 가장 상단의 식이므로 대충 행렬을 만들어본다.

 

일단 좌변에 결과를 두고, 우변에 과정을 둔다. 

 

Fn = (행렬)*(행렬)

 

이런 형식을 우리는 원하는데 

 

우변의 두 행렬 중 

 

오른쪽 행렬은 Fn-1, Fn-2가 들어가고

왼쪽 행렬을 그 계수가 들어가면 된다. 

 

따라서 우리는 가장 중요한 식에 중점을 두고 그렇게 만들게 한뒤에 나머지를 잘 맞게끔 행렬을 만든다. 

그 뒤에 이제 계수로 만들어진 행렬을 분할정복을 이용해서 구하면 된다. 

 

 

 

자 이제 생각해보아야 하는게 k와 n이 있는데 그러면 어떤식으로 점화식을 찾을까이다. 

 

n의 크기가 엄청나게 커서 우리는 이 방법을 쓰는 것이기 때문에, An = 행렬*An-1 이런 꼴로 만들어야 한다. 

그래야 An = (행렬)^n * A0 이런식으로 표현할 수 있고, 결과를 찾을 수 있다. 

 

만약에 그러면 k에 대해서만 저런 점화식이 세워진다면? 그건 사실 모른다. 아무튼 이제 저런 n에 관한 점화식을 세워야한다. 방향을 잡은것과 아닌것과는 진짜 엄청나게 다르다. 

 

점화식을 찾는것은 규칙을 찾는것이라서 그냥 경험에 토대로 여러가지를 해보고, 규칙을 찾는다. 

 

여기에서는 

 

S(k,n) = 1+S(0,n-1)+S(1,n-1)+ ... + S(k, n-1)이렇게 되었다. 

 

규칙찾는건 구글링하면 잘 나온다.

 

위 점화식을 찾은 상태에서 이제 우리가 피보나치식을 세운것처럼 이제 행렬을 만든다. 

저것이 되게 만든다음에 나머지를 알아서 채워넣으면 된다. 

 

이제 분할정복을 이용해서 (행렬)^n을 풀어야하는데 사실 아직 logn의 거듭제곱이 잘 이해가 안가는 면이 조금 있다.

 

따라서 43 = 32+8+2+1 나는 이런 방법을 이용해서 대충 O((logn)^2)의 풀이로 풀었다. 

 

나는 행렬이 교육과정에 있어서 배웠었는데 행렬이 어떤건지 이제까지 몰랐었다. 지금도 안다고 할 수 있는 수준은 아니지만 그래도 훨씬 더 행렬이 어떤식으로 쓰이는지 옛날에 수학은 도구라고 했었던 말이 무슨 말인지 이해가 조금씩 되는 것 같다.

 

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int MAX = 55;

int k;

struct mat { // 2차원 구조체 
	ll m[MAX][MAX];
};

struct mat ans;
struct mat use;
struct mat tmp;

mat operator*(const mat &a, const mat &b) { // 행렬곱 연산 
	struct mat v;
	int n = k + 2;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ll r = 0;
			for (int t = 0; t < n; t++) {
				r += a.m[i][t] * b.m[t][j];
				r %= MOD;
			}
			v.m[i][j] = r;
		}
	}
	return v;
}

int main() {
	int n;
	cin >> k >> n;
	for (int i = 0; i < k + 2; i++) {
		for (int j = 0; j < k + 2; j++) {
			if (i >= j)	use.m[i][j] = 1;  // 우리가 찾은 행렬점화식
			else use.m[i][j] = 0;
			if (i == j)ans.m[i][j] = 1; // 어떤거와 곱했을때 어떤거가 되는 단위행렬 
			else ans.m[i][j] = 0;
		}
	}
	int cnt = 1;
	tmp = use;
	while (n > 0) {  // 43  = 32 + 8 + 2 + 1 이런식으로 행렬을 쪼개어 계산 
		while (n > cnt*2) {
			cnt *= 2;
			tmp = tmp * tmp;
		}
		if(n==cnt){
			n -= cnt;
			ans = ans * tmp;
		}
		else if(n>cnt){
			n -= cnt;
			ans = ans * tmp;
			tmp = use;
			cnt = 1;
		}
	}
	ll res = 0;
	res = ans.m[k + 1][0];
	res %= MOD;

	cout << res;
}