[BOJ] 백준 16467. 병아리의 변신은 무죄 (Gold I)

재밌는 문제이다.

문제는 아래와 같다.

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

16467번: 병아리의 변신은 무죄

처음엔 단순 dp일 줄 알았는데 K가 tc마다 달라지므로 dp table을 전처리로 시간내에 처리하기엔 무리가 있었다.

이번 포스팅에서 풀이 과정을 마저 설명해보겠다.

 

***혹시나 예제가 제대로 나오는데 맞왜틀하시는 분들을 위해***

나머지가 1e9+7이 아니라 1e8+7이다! 

---

의식의 흐름 및 해설

병아리의 알이 K일 후에 깨어나며,

병아리는 매일매일 알을 낳는다.

 

현재 병아리의 수만큼 알을 낳으며, 이 때 낳은 알들은 K일 후에 모두 깨어난다.

따라서 우리는 점화식을 d[n]=d[n-1]+d[n-K-1]로 세울 수 있다.

d[n-1]은 어제 병아리인 애들은 당연히 오늘도 병아리이기 때문이다.

만약, 점화식이 잘 보이지 않는다면 수를 나열해보면 쉽게 보인다.

 

문제는, d[n]=d[n-1]+d[n-K-1]에서 K만 없었다면 N<=1e8이므로 충분히 시간 내에 돌아갈 것이라 예상할 수 있다.

그러나, 1<=K<=10이기 때문에 따로 전처리를 하기엔 시간 내에 돌아가지 않을 듯하다.

 

다행히 점화식의 꼴이 An=C1An-1 + C2An-2 + ... + Ck+1An-k-1 꼴이기 때문에 행렬 거듭제곱 dp로 처리할 수 있어보인다! 이를 이용하면 O(T*K^3lgN)에 처리할 수 있다.

 

행렬식에 익숙하지 않아 처음엔 An-2, An-3, ..., An-k 에는 전부 0을 씌워줬는데, 

그렇게 하면 거듭제곱이 이루어지지 않으므로 주의하자.

 

행렬식을 맘대로 못세운다면 아래 블로그가 큰 도움이 될 것이다.

나도 예전에 이 블로그랑 kks227님의 블로그 덕분에 점화식을 행렬로 세우는 포인트를 알게 됐다.

https://driip.me/00556a4c-0782-4c5b-a86a-8e27e5f4ac1b

행렬 거듭제곱을 이용한 선형 점화식의 DP 풀기

 

그리고 이 문제의 가장 큰 주의할점!

나머지가 1e9+7이 아니라 1e8+7이다! 

 

나 외에도 수많은 피해자(?)가 존재하므로 주의하도록 하자.

---

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
const int MAX = 300011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const ll MOD = 1e8 + 7;
int t, K, N;
class Matrix {
public:
	vector<vector<ll>> v;
	Matrix() {
		v = vector<vector<ll>>(K + 2, vector<ll>(K + 2, 0));
	}
	Matrix operator*(const Matrix O) const {
		Matrix R;
		for (int i = 0; i < K + 2; i++) {
			for (int j = 0; j < K + 2; j++) {
				for (int k = 0; k < K + 2; k++) {
					R.v[i][j] += v[i][k] * O.v[k][j];
					R.v[i][j] %= MOD;
				}
			}
		}
		return R;
	}
};
Matrix power(Matrix M, ll k) {
	Matrix R;
	if (!k) {
		for (int i = 0; i < K + 2; i++) {
			R.v[i][i] = 1;
			return R;
		}
	}
	if (k == 1)return M;
	R = power(M, k / 2);
	R = R * R;
	if (k % 2)
		R = R * M;
	return R;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> t;
	while (t--) {
		cin >> K >> N;
		Matrix A;
		for (int i = 0; i < K + 2; i++) {
			for (int j = 0; j < K + 2; j++) {
				if (i - j == 1)
					A.v[i][j] = 1;
				else
					A.v[i][j] = 0;
			}
		}
		A.v[0][0] += 1;
		A.v[0][K] += 1;
		A = power(A, 1LL*N - 1);
		cout << (A.v[0][0] + A.v[K][0]) % MOD << "\n";
	}
}

---

굉장히 재밌게 풀었다.