Algorithm in A..Z - Matrix Multiplication

행렬의 곱셈

크기가 A * B인 X 행렬과 크기가 B * C인 행렬 Y의 곱의 결과 Z는 A * C의 행렬이다. (A의 열의 개수와 B의 행의 개수는 같아야 한다.)

C 행렬의 (i, j)는 A의 i행의 성분 * B의 j열의 성분의 합이다.

곱셈의 항등원 (단위행렬 : Unit Matrix)

왼쪽 위에서 오른쪽 아래로 (↘) 1인 행렬이다. 기호 E

---

시간 복잡도

N1*M 행렬과 M*N2 행렬의 시간 복잡도는 O(N1 * N2 * M)

---

코드

vector<vector<long long>> operator*=(vector<vector<long long>> &x, vector<vector<long long>> const &y) {
    vector<vector<long long>> result(x.size(), vector<long long>(y.front().size(), 0L));
    for (int i = 0;i < x.size();++i) {
        for (int j = 0;j < y.size();++j) {
            for (int k = 0;k < y.front().size();++k) {
                result[i][j] += x[i][k] * y[k][j];
                result[i][j] %= MOD;
            }
        }
    }


    return result;
}

---

응용 (경우의 수)

A, B, C가 서로 연결된 그래프를 인접행렬로 표시하면

(AA) (AB) (AC)    0 1 1
(BA) (BB) (BC) => 1 0 1
(CA) (CB) (CC)    1 1 0

인접행렬을 제곱하면

2 1 1
1 2 1
1 1 2

1행 1열을 보면 간선을 2개 거쳐서 가는 경우의 수가 나온다.

AA * AA + AB * BA + AC + CA
=> 0 + 1 + 1 = 2

인접행렬을 세제곱하면

2 3 3
3 2 3
3 3 2

간선을 3개 거쳐서 가는 경우의 수가 나온다.

 

즉 행렬의 N번 제곱하면 간선을 N개 거쳐서 가는 경우의 수다.

www.acmicpc.net/problem/14289

14289번: 본대 산책 3

#include <bits/stdc++.h>
using namespace std;

constexpr long long MOD = 1000000007L;

vector<vector<long long>> operator*(vector<vector<long long>> const& x, vector<vector<long long>> const& y) {
    vector<vector<long long>> result(x.size(), vector<long long>(y.front().size(), 0L));
    for (int i = 0;i < x.size();++i) {
        for (int j = 0;j < y.size();++j) {
            for (int k = 0;k < y.front().size();++k) {
                result[i][j] += x[i][k] * y[k][j];
                result[i][j] %= MOD;
            }
        }
    }

    return result;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<long long>> matrix(n, vector<long long>(n ,0L));
    while (m--) {
        int a, b;
        cin >> a >> b;

        matrix[a - 1][b - 1] = 1L;
        matrix[b - 1][a - 1] = 1L;
    }

    vector<vector<long long>> result(n, vector<long long>(n, 0L));
    for (int i = 0;i < n;++i) {
        result[i][i] = 1L;
    }

    int time;
    cin >> time;
    while (time) {
        if (time % 2 == 1) {
            result = result*matrix;
        }

        matrix = matrix*matrix;
        time /= 2;
    }

    cout << result[0][0] << "\n";
}