행렬

행렬이란?

수를 가로와 세로로 배열한 것. N행 M열의 크기를 가지는 행렬을 $N\times M$ 행렬이라고 함

행렬의 덧셈

$\begin{pmatrix} 3,1,4,1\\ 5,9,2,6\\ 5,3,5,8 \end{pmatrix}+ \begin{pmatrix} 1,4,1,4\\ 2,1,3,5\\ 6,2,3,7 \end{pmatrix}= \begin{pmatrix} 4,5,5,5\\ 7,10,5,11\\ 11,5,8,15 \end{pmatrix}$
이 처럼 각각의 행과 열의 인덱스가 같은 것끼리 더한값을 가지게 됩니다. 뺄셈 역시 동일합니다.

행렬의 곱셈

행의 곱의 경우는 행렬 A의 열과 행렬 B의 행의 수가 같을 때만 계산 할 수 있으며, 행렬끼리의 곱의 행렬은 A행렬의 행인 N과 B행렬의 열인 M의 크기를 가지게 됩니다. 이해를 돕기위해 다음의 예시를 보겠습니다.
$\begin{pmatrix} 3,1,4,1,5\ 9,2,6,5,3\ 5,8,9,7,9\ 3,2,3,8,4 \end{pmatrix}+ \begin{pmatrix} 1,4,1\ 4,2,1\ 3,5,6\ 2,3,7\ 3,0,9 \end{pmatrix}= \begin{pmatrix} 36,37,80\ 54,85,109\ 105,102,197\ 48,55,115 \end{pmatrix} $
A 행렬은 4행 5열, B 행렬은 5행 3열입니다. B 행열의 행과 A 행열의 열의 크기가 같기에 행렬의 곱을 할 수 있습니다.
또한 결과 행렬의 값은 어떤 식으로 정해지는 가에 대해서는 예시로 결과 행렬의 2행 2열의 값을 구하는 방법은 다음과 같습니다.

A 행렬의 2행인 [9, 2, 6, 5, 3] 과 B 행렬의 2열인 [4, 2, 5, 3, 0]을 찾습니다.
각 배열의 같은 인덱스끼리 곱한 배열을 구합니다.
[ 9, 2, 6, 5, 3]
[ 4, 2, 5, 3, 0]
[36, 4, 30, 15, 0]
결과 배열의 합이 결과 행렬의 2행 2열의 값입니다.
36+4+30+15+0=85

행렬의 곱에서 주의할 점은 교환법칙($AB=BA$)가 성립하지 않습니다
하지만 결합법칙($A(BC)=(AB)C$)은 성립합니다.

행렬의 거듭제곱

이것이 성립되기 위해서는 피 연산자는 행과 열이 같아야 합니다. 또한 A 행렬의 제곱을 $A^2$이라고 할 때,
$A^2\times A^2=A^4$
임을 알 수 있는데, 이는 결합법칙이 성립하기에 가능한 것입니다.

행렬로 피보나치 수열의 아래 9자리 숫자 구하기

$\begin{pmatrix} 1,1\ 1,0 \end{pmatrix} $
행렬의 거듭제곱을 하고 $A^n$의 2번째 행의 합을 구하면 n+1번째 피보나치를 구할수 있습니다.

빠르게 계산하는 법

구하고자하는 인덱스를 고르고, 그 값에서 1을 뺀 값을 이진법으로 변환합니다. ex) 12= 1100(8+4)
행렬의 거듭제곱을 통하여 이진법으로 분류된 행렬을 구합니다
$A^8\times A^4=A^{12}$
$\begin{pmatrix} 34,21\\ 21,13 \end{pmatrix} \times \begin{pmatrix} 5,3\\ 3,2 \end{pmatrix} = \begin{pmatrix} 233,144\\ 144,89 \end{pmatrix}$
행렬의 2번째 항의 합을 구하면 정한 인덱스에 맞는 피보나치의 값을 계산할 수 있다.
$144+89=233$

구현

#include <iostream>
#include <vector>
#include<queue>

#define MOD 1000000007

using namespace std;

struct Matrix 
{
    vector<vector<long long int>> data;
};

Matrix multiply(const Matrix& A, const Matrix& B) 
{
    Matrix result;
    result.data.resize((long long int)2, vector<long long int>(2, 0));

    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) 
            {
                result.data[i][j] += (A.data[i][k] * B.data[k][j])%MOD;
            }
        }
    }

    return result;
}

int main() 
{
    int N;
    cin >> N;

    Matrix begin;
    begin.data = {{1, 1}, {1, 0}};

    queue<int> binary;
    N--;
    while(N>0)
    {
        binary.push(N%2);
        N/=2;
    }
    Matrix result = begin;
    Matrix temp;
    temp.data={{1,0},{0,1}};
    while(!binary.empty())
    {
        int bit =binary.front();
        binary.pop();
        if(bit==1)
        {
            temp = multiply(temp,result);
        }
        result = multiply(result,result);

    }

    cout << (temp.data[1][0] + temp.data[1][1])%MOD;

    return 0;
}

struct Matrix - 이차원 배열을 저장할 구조체
Matrix multiply(const Matrix& A, const Matrix& B) - 입력받은 행렬 두개를 곱하여 주는 함수

입력한 숫자를 2진수의 단위로 쪼개는 작업

while(N>0)
    {
        binary.push(N%2);
        N/=2;
    }

$2\times 2$ 행렬에서 곱했을시 그대로인 행렬
```
temp.data={{1,0},{0,1}};
```

while(!binary.empty())
    {
        int bit =binary.front();
        binary.pop();
        if(bit==1)
        {
            temp = multiply(temp,result);
        }
        result = multiply(result,result);

    }

cout << result.data[1][0] + result.data[1][1]; - 결과 출력
N--; - --인 이유는 begin함수에 하나가 이미 존재하기 때문