18287번: 체스판 이동
크기가 N×M인 체스판이 있다. 체스판의 행 번호는 위에서부터 1, 2, ..., N이고, 열 번호는 왼쪽에서부터 1, 2, ..., M이다. 체스판의 각 칸은 (i, j)로 표현하고, i는 행 번호, j는 열 번호이다. 체스판의
www.acmicpc.net
우선 체스판이 어떻게 생겼는지 알아야 합니다.
검정색 칸을 $B$, 흰색 칸을 $W$라고 표현할 때 체스판의 생김새는 다음과 같습니다.
$\begin{matrix}B & W & B & W & \cdots\\ W & B & W & B & \cdots\\ \vdots & \vdots & \vdots & \vdots & \ddots\end{matrix}$
$M$을 적당히 큰 수라고 생각해보면,
$N$번 행에 도착하는 방법은 다음의 합이 됩니다.
$\left ( N,1 \right )$에 도착하는 방법
$\left ( N,2 \right )$에 도착하는 방법
$\vdots$
$\left ( N,M \right )$에 도착하는 방법
이제 $\left ( i,j \right )$에 도착하는 방법을 $R\left ( i,j \right )$ 라고 해봅시다.
가장 먼저 $N$이 짝수일 때, $R\left ( N+1,1 \right )$ 을 구해보겠습니다.
이동은 항상 행 번호가 증가하는 쪽으로만 할 수 있습니다.
즉, 수직 아래, 왼쪽 아래 대각선, 오른쪽 아래 대각선 세 방향으로만 이동할 수 있다는 뜻입니다.
$N$이 짝수인 경우를 계산 중이므로, $\left ( N+1,1 \right )$ 으로 이동할 수 있는 칸은
$\left ( N,1 \right )$
$\left ( N,2 \right )$
두 칸이 됩니다.
같은 이유로 $\left ( N+1,2 \right )$ 으로 이동할 수 있는 칸은 $\left ( N,1 \right )$, $\left ( N,2 \right )$, $\left ( N,3 \right )$ 입니다.
결과적으로 다음을 얻을 수 있습니다.
$R\left ( N+1,j \right )=\left\{\begin{matrix}R\left ( N,1 \right )+R\left ( N,2 \right ) & j=1\\R\left ( N,j-1 \right )+R\left ( N,j \right )+R\left ( N,j+1 \right ) & 2\leq j< M\\ R\left ( N,M-1 \right )+R\left ( N,M \right ) & j=M\end{matrix}\right.$
(단, $N$ 은 짝수)
이제 $N$이 홀수일 때도 같은 과정을 거치면 다시 다음을 얻습니다.
$R\left ( N+1,j \right )=\left\{\begin{matrix}R\left ( N,2 \right ) & j=1\\R\left ( N,j-1 \right )+R\left ( N,j+1 \right ) & 2\leq j< M\\R\left ( N,M \right ) & j=M\end{matrix}\right.$
(단, $N$은 홀수)
$N$이 짝수인지, 홀수인지에 따라 점화식의 형태가 변했습니다.
이때 짝수와 홀수 둘을 아우르는 점화식을 발견하려고 할 수도 있겠지만,
저의 경우 그냥 각각의 행렬 점화식을 구하여 끝냈습니다.
먼저 $N$이 짝수일 경우,
$\begin{bmatrix}R\left(N+1,1 \right)\\ R\left(N+1,2 \right)\\ R\left(N+1,3 \right)\\ \vdots\\R\left(N+1,M-2 \right)\\ R\left(N+1,M-1 \right)\\ R\left(N+1,M \right)\end{bmatrix}=\begin{bmatrix}1 & 1 & 0 & 0 & \cdots & 0 & 0 & 0 & 0\\ 1 & 1 & 1 & 0 & \cdots & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & \cdots & 0 & 0 & 0 & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots\\ 0 & 0 & 0 & 0 & \cdots & 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & \cdots & 0 & 1 & 1 & 1\\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 & 1 & 1\end{bmatrix}\begin{bmatrix}R\left(N,1 \right)\\ R\left(N,2 \right)\\ R\left(N,3 \right)\\ \vdots\\ R\left(N,M-2 \right)\\ R\left(N,M-1 \right)\\ R\left(N,M \right)\end{bmatrix}$
그리고 $N$이 홀수일 경우,
$\begin{bmatrix}R\left(N+1,1 \right)\\ R\left(N+1,2 \right)\\ R\left(N+1,3 \right)\\ \vdots\\R\left(N+1,M-2 \right)\\ R\left(N+1,M-1 \right)\\ R\left(N+1,M \right)\end{bmatrix}=\begin{bmatrix}0 & 1 & 0 & 0 & \cdots & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & \cdots & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & \cdots & 0 & 0 & 0 & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots\\ 0 & 0 & 0 & 0 & \cdots & 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & \cdots & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 & 1 & 0\end{bmatrix}\begin{bmatrix}R\left(N,1 \right)\\ R\left(N,2 \right)\\ R\left(N,3 \right)\\ \vdots\\ R\left(N,M-2 \right)\\ R\left(N,M-1 \right)\\ R\left(N,M \right)\end{bmatrix}$
이렇게 점화식을 얻을 수 있습니다.
두 식을 편의상 다음과 같이 나타내겠습니다.
$N$이 짝수일 때,
$\begin{bmatrix}R\left(N+1,1 \right)\\ R\left(N+1,2 \right)\\ R\left(N+1,3 \right)\\ \vdots\\R\left(N+1,M-2 \right)\\ R\left(N+1,M-1 \right)\\ R\left(N+1,M \right)\end{bmatrix}=\begin{bmatrix} BASE_{1}\end{bmatrix}\begin{bmatrix}R\left(N,1 \right)\\ R\left(N,2 \right)\\ R\left(N,3 \right)\\ \vdots\\ R\left(N,M-2 \right)\\ R\left(N,M-1 \right)\\ R\left(N,M \right)\end{bmatrix}$
그리고 $N$이 홀수일 때,
$\begin{bmatrix}R\left(N+1,1 \right)\\ R\left(N+1,2 \right)\\ R\left(N+1,3 \right)\\ \vdots\\R\left(N+1,M-2 \right)\\ R\left(N+1,M-1 \right)\\ R\left(N+1,M \right)\end{bmatrix}=\begin{bmatrix} BASE_{2}\end{bmatrix}\begin{bmatrix}R\left(N,1 \right)\\ R\left(N,2 \right)\\ R\left(N,3 \right)\\ \vdots\\ R\left(N,M-2 \right)\\ R\left(N,M-1 \right)\\ R\left(N,M \right)\end{bmatrix}$
최종적으로 다음을 구현하면 됩니다.
$\begin{bmatrix}R\left(2k+1,1 \right)\\ R\left(2k+1,2 \right)\\ R\left(2k+1,3 \right)\\ \vdots\\R\left(2k+1,M-2 \right)\\ R\left(2k+1,M-1 \right)\\ R\left(2k+1,M \right)\end{bmatrix}=\begin{bmatrix} BASE_{1}\end{bmatrix}^{K}\begin{bmatrix}BASE_{2} \end{bmatrix}^{K}\begin{bmatrix}R\left(1,1 \right)\\ R\left(1,2 \right)\\ R\left(1,3 \right)\\ \vdots\\ R\left(1,M-2 \right)\\ R\left(1,M-1 \right)\\ R\left(1,M \right)\end{bmatrix}$
$\begin{bmatrix}R\left(2k,1 \right)\\ R\left(2k,2 \right)\\ R\left(2k,3 \right)\\ \vdots\\R\left(2k,M-2 \right)\\ R\left(2k,M-1 \right)\\ R\left(2k,M \right)\end{bmatrix}=\begin{bmatrix} BASE_{1}\end{bmatrix}^{K-1}\begin{bmatrix}BASE_{2} \end{bmatrix}^{K}\begin{bmatrix}R\left(1,1 \right)\\ R\left(1,2 \right)\\ R\left(1,3 \right)\\ \vdots\\ R\left(1,M-2 \right)\\ R\left(1,M-1 \right)\\ R\left(1,M \right)\end{bmatrix}$
이렇게 구현하면, 대부분의 케이스는 해결됐습니다.
이제부터는 이 방법으로 구할 수 없는 케이스들을 알고 그것들을 예외처리하는 과정입니다.
첫번째는 $N=1$인 케이스입니다.
$N=1$일 경우 한번 출발할 지점을 정하면 더 이상 이동을 할 필요가 없이 끝입니다.
즉 $R\left ( 1,k \right )=1$ 입니다. (단, $1\leq k\leq M$)
따라서 출발지점으로 고를 수 있는 열의 개수 $M$이 답이 됩니다.
두번째는 $N>1$ 이고 동시에 $M=1$ 인 케이스입니다.
이 경우, $1$번 행에서 더 이상 움직일 수 있는 칸이 없습니다.
따라서 $N$번 행에 도착하는 방법의 수가 0이 됩니다.
마지막으로, $M=2$인 케이스입니다.
$M=2$ 일 때는 아주 독특한 해답이 나오니 직접 구해보는 게 좋습니다.
$N=1$ 일 때, $R\left ( 1,1 \right)=R\left ( 1,2 \right)=1$ 입니다.
$N=2$ 일 때, $R\left ( 2,1 \right)=R\left ( 2,2 \right)=1$ 입니다.
$N=3$ 일 때, $R\left ( 3,1 \right)=R\left ( 3,2 \right)=2$ 입니다.
$N=4$ 일 때, $R\left ( 4,1 \right)=R\left ( 4,2 \right)=2$ 입니다.
$N=5$ 일 때, $R\left ( 5,1 \right)=R\left ( 5,2 \right)=4$ 입니다.
$N=6$ 일 때, $R\left ( 6,1 \right)=R\left ( 6,2 \right)=4$ 입니다.
$N=7$ 일 때, $R\left ( 7,1 \right)=R\left ( 7,2 \right)=8$ 입니다.
$N=8$ 일 때, $R\left ( 8,1 \right)=R\left ( 8,2 \right)=8$ 입니다.
즉 답은 $2^{\large \left \lceil \frac{N}{2} \right \rceil}$ 입니다.
이제 모든 케이스에 대한 답이 나오도록 구현하면 됩니다.
코드는 다음과 같습니다.
#include <stdio.h>
#define mod 1000000007
typedef struct {
long long array[30][30];
} Matrix;
void Matrix_print (Matrix object, int size);
long long power_modular (long long base, long long power);
Matrix matrix_multiply_modular (Matrix A, Matrix B, int size);
Matrix matrix_power_modular (Matrix A, long long power, int size);
int main() {
long long N;
int M;
scanf("%lld %d", &N, &M);
if (N == 1) {
printf("%d", M);
return 0;
}
else if (M == 1) { // N > 1, M = 1
printf("0");
return 0;
}
else if (M == 2) {
long long answer;
if (N % 2) {
answer = power_modular(2, (N+1)/2);
}
else {
answer = power_modular(2, N/2);
}
printf("%lld", answer);
return 0;
}
else {
int size = M;
Matrix Answer;
for (int i = 0; i < size; i++) {
Answer.array[i][0] = 1;
for (int j = 1; j < size; j++) {
Answer.array[i][j] = 0;
}
}
Matrix Base1;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i == 0) {
if (j <= 1) {
Base1.array[i][j] = 1;
}
else {
Base1.array[i][j] = 0;
}
}
else if (i == size - 1) {
if (j >= size - 2) {
Base1.array[i][j] = 1;
}
else {
Base1.array[i][j] = 0;
}
}
else {
if (j == i - 1 || j == i || j == i + 1) {
Base1.array[i][j] = 1;
}
else {
Base1.array[i][j] = 0;
}
}
}
}
Matrix Base2;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i == 0) {
if (j == 1) {
Base2.array[i][j] = 1;
}
else {
Base2.array[i][j] = 0;
}
}
else if (i == size - 1) {
if (j == size - 2) {
Base2.array[i][j] = 1;
}
else {
Base2.array[i][j] = 0;
}
}
else {
if (j == i - 1 || j == i + 1) {
Base2.array[i][j] = 1;
}
else {
Base2.array[i][j] = 0;
}
}
}
}
long long power = N / 2;
if (N % 2) {
Base1 = matrix_power_modular(Base1, power, size);
}
else {
Base1 = matrix_power_modular(Base1, power - 1, size);
}
Base2 = matrix_power_modular(Base2, power, size);
Answer = matrix_multiply_modular(Base2, Answer, size);
Answer = matrix_multiply_modular(Base1, Answer, size);
long long answer = 0;
for (int i = 0; i < M; i++) {
answer = (answer + Answer.array[i][0]) % mod;
}
printf("%lld", answer);
return 0;
}
}
void Matrix_print (Matrix object, int size) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
printf("%lld ", object.array[i][j]);
}
printf("\n");
}
printf("\n");
}
long long power_modular(long long base, long long power) {
base %= mod;
long long result = 1;
while(power) {
if (power % 2) {
result = (result * base) % mod;
}
base = (base * base) % mod;
power /= 2;
}
return result;
}
Matrix matrix_multiply_modular (Matrix A, Matrix B, int size) {
Matrix result;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
result.array[i][j] = 0;
for (int k = 0; k < size; k++) {
long long temp = (A.array[i][k] * B.array[k][j]) % mod;
result.array[i][j] = (result.array[i][j] + temp) % mod;
}
}
}
return result;
}
Matrix matrix_power_modular (Matrix A, long long power, int size) {
Matrix result;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i == j) {
result.array[i][j] = 1;
}
else {
result.array[i][j] = 0;
}
}
}
while(power) {
if (power % 2) {
result = matrix_multiply_modular (result, A, size);
}
A = matrix_multiply_modular (A, A, size);
power /= 2;
}
return result;
}
(C11, 1116KB, 12ms, 제출번호 26334509)
다른 문제들에선 Base 역할을 하는 행렬이 하나만 있었는데
이 문제에선 두 개를 써서 신선한 문제였습니다.
'분할 정복을 이용한 거듭제곱 > 행렬 거듭제곱' 카테고리의 다른 글
| 백준 12728번: n제곱 계산 (0) | 2021.02.28 |
|---|---|
| 백준 12925번: Numbers (0) | 2021.02.28 |
| 백준 9341번: ZZ (0) | 2021.02.19 |
| 백준 13430번: 합 구하기 (0) | 2021.02.19 |
| 백준 16467번: 병아리의 변신은 무죄 (0) | 2021.02.19 |