Gerak Kuda

2024-06-13Updated on 2024-06-20

Soal#

Informasi#

  • Sumber: CompFest 7 - Final CPC Junior

Arsip#

Ringkasan#

Diberikan sebuah papan catur dengan ukuran 5 baris dan $N$ ($1 \le N \le 10^9$) kolom. Untuk setiap baris pada kolom pertama, hitunglah banyak cara (modulo $10^9 + 7$) agar bidak kuda sampai kolom ke-$N$! Bidak kuda harus selalu bergerak ke arah kanan dan tidak boleh keluar papan.

Solusi#

Petunjuk#

+
Petunjuk 1
+
Petunjuk 2
+
Petunjuk 3

Pembahasan#

Mencari solusi awal#

Kita bisa menggunakan relasi rekurensi untuk menyelesaikan permasalahan ini. Mari kita cari tahu bagaimana pergerakan bidak apabila bidak berada pada baris ke-1 sampai ke-5 kolom ke-$n$.

  • Apabila bidak berada pada baris ke-1, maka bidak dapat mengunjungi
    • Baris ke-3 kolom ke-$(n + 1)$
    • Baris ke-2 kolom ke-$(n + 2)$
  • Apabila bidak berada pada baris ke-2, maka bidak dapat mengunjungi
    • Baris ke-4 kolom ke-$(n + 1)$
    • Baris ke-1 kolom ke-$(n + 2)$
    • Baris ke-3 kolom ke-$(n + 2)$
  • Apabila bidak berada pada baris ke-3, maka bidak dapat mengunjungi
    • Baris ke-1 kolom ke-$(n + 1)$
    • Baris ke-5 kolom ke-$(n + 1)$
    • Baris ke-2 kolom ke-$(n + 2)$
    • Baris ke-4 kolom ke-$(n + 2)$
  • Apabila bidak berada pada baris ke-4, maka bidak dapat mengunjungi
    • Baris ke-2 kolom ke-$(n + 1)$
    • Baris ke-3 kolom ke-$(n + 2)$
    • Baris ke-5 kolom ke-$(n + 2)$
  • Apabila bidak berada pada baris ke-5, maka bidak dapat mengunjungi
    • Baris ke-3 kolom ke-$(n + 1)$
    • Baris ke-4 kolom ke-$(n + 2)$

Misal $f(k, n)$ menyatakan banyaknya cara agar mencapai baris ke-$k$ kolom ke-$n$ dari kanan. Berdasarkan pergerakan bidak di atas, maka

  • $f(1, n) = f(3, n + 1) + f(2, n + 2)$
  • $f(2, n) = f(4, n + 1) + f(1, n + 2) + f(3, n + 2)$
  • $f(3, n) = f(1, n + 1) + f(5, n + 1) + f(2, n + 2) + f(4, n + 2)$
  • $f(4, n) = f(2, n + 1) + f(3, n + 2) + f(5, n + 2)$
  • $f(5, n) = f(3, n + 1) + f(4, n + 2)$

dengan kasus dasar $f(k, N) = 0$ dan $f(k, N - 1) = 1$ untuk setiap $k \in \{1, 2, 3, 4, 5\}$.

Karena saya lebih suka membangun sebuah solusi dari solusi-solusi yang lebih kecil, maka $f(k, n)$ dapat didefinisikan menjadi

  • $f(1, n) = f(3, n - 1) + f(2, n - 2)$
  • $f(2, n) = f(4, n - 1) + f(1, n - 2) + f(3, n - 2)$
  • $f(3, n) = f(1, n - 1) + f(5, n - 1) + f(2, n - 2) + f(4, n - 2)$
  • $f(4, n) = f(2, n - 1) + f(3, n - 2) + f(5, n - 2)$
  • $f(5, n) = f(3, n - 1) + f(4, n - 2)$

dengan kasus dasar $f(k, 0) = 0$ dan $f(k, 1) = 1$ untuk setiap $k \in \{1, 2, 3, 4, 5\}$. Selain itu, definisi ini juga lebih intuitif karena $f(k, n)$ bergantung pada nilai di kiri kolom ke-$n$.

Jawaban akhir dari permasalahan ini adalah nilai dari $(f(1, N) + f(2, N) + f(3, N) + f(4, N) + f(5, N)) \bmod (10^9 + 7)$, atau

$$\left(\sum_{k = 1}^5 f(k, N)\right) \bmod (10^9 + 7)$$

Berikut adalah contoh solusi yang menggunakan relasi rekurensi.

#include <iostream>
using namespace std;
typedef long long int lli;

const int MOD = 1E9 + 7;

int f(int k, int n){
    if(n == 0) return 0;
    if(n == 1) return 1;
    
    if(k == 1)
        return ((lli)f(3, n - 1) + f(2, n - 2)) % MOD;
    if(k == 2)
        return ((lli)f(4, n - 1) + f(1, n - 2) + f(3, n - 2)) % MOD;
    if(k == 3)
        return ((lli)f(1, n - 1) + f(5, n - 1) + f(2, n - 2) + f(4, n - 2)) % MOD;
    if(k == 4)
        return ((lli)f(2, n - 1) + f(3, n - 2) + f(5, n - 2)) % MOD;
    if(k == 5)
        return ((lli)f(3, n - 1) + f(4, n - 2)) % MOD;
    return 0;
}

int N;

int main(){
    cin >> N;
    cout << ((lli)f(1, N) + f(2, N) + f(3, N) + f(4, N) + f(5, N)) % MOD << '\n';
}

Optimisasi dengan dynamic programming#

Pada solusi sebelumnya, $f(k, n)$ untuk suatu $k$ dan $n$, dipanggil berkali-kali walaupun memiliki nilai yang sama. Hal ini dapat memperlambat running time dari program dengan solusi tersebut. Untungnya, kita bisa memanggil $f(k, n)$ untuk suatu $k$ dan $n$, hanya sekali saja dan menyimpan hasilnya pada sebuah tabel. Teknik ini juga sering disebut sebagai teknik dynamic programming.

Berikut adalah modifikasi dari solusi sebelumnya dengan menggunakan teknik dynamic programming.

#include <iostream>
using namespace std;
typedef long long int lli;

const int MOD = 1E9 + 7;
const int MAXN = 1000;

int dp[6][MAXN + 1];

int f(int k, int n){
    if(n == 0) return 0;
    if(n == 1) return 1;

    int& ret = dp[k][n];
    if(ret != -1) return ret;
    
    if(k == 1)
        ret = ((lli)f(3, n - 1) + f(2, n - 2)) % MOD;
    if(k == 2)
        ret = ((lli)f(4, n - 1) + f(1, n - 2) + f(3, n - 2)) % MOD;
    if(k == 3)
        ret = ((lli)f(1, n - 1) + f(5, n - 1) + f(2, n - 2) + f(4, n - 2)) % MOD;
    if(k == 4)
        ret = ((lli)f(2, n - 1) + f(3, n - 2) + f(5, n - 2)) % MOD;
    if(k == 5)
        ret = ((lli)f(3, n - 1) + f(4, n - 2)) % MOD;
    return ret;
}

int N;

int main(){
    cin >> N;
    for(int i = 1; i <= 5; i++){
        for(int j = 0; j <= N; j++){
            dp[i][j] = -1;
        }
    }

    cout << ((lli)f(1, N) + f(2, N) + f(3, N) + f(4, N) + f(5, N)) % MOD << '\n';
}

Perhatikan bahwa tabel (atau array dua dimensi) dp pada solusi di atas merepresentasikan nilai dari $f(k, n)$ (dp[k][n]). Perhatikan pula tidak semua nilai $n$ yang mungkin dapat direpresentasikan karena nilai MAXN hanyalah 1000. Hal ini disebabkan karena apabila nilai MAXN adalah 1000000000 ($10^9$ sesuai batasan pada soal), maka solusi akan menggunakan memori yang sangat besar sehingga tidak memenuhi batasan memori pada soal. Oleh karena itu, solusi tersebuh harus dioptimisasi lagi.

Optimisasi dengan matrix exponentiation#

Kita bisa menggunakan matrix exponentiation untuk menyelesaikan soal ini dengan menggunakan sedikit memori. Coba baca blog dan video dari Errichto untuk memahami teknik ini. Intinya, beberapa rekurensi dapat direpresentasikan dengan perkalian matriks dan vektor. Bentuk yang biasanya digunakan adalah

$$v' = Av$$

di mana $v'$ dan $v$ adalah vektor yang berisi beberapa nilai dari rekurensi dan $A$ adalah matriks untuk mengubah (transformasi) $v$ menjadi $v'$.

Misalnya pada kasus rekurensi untuk menghitung bilangan Fibonacci: $F(n) = F(n - 1) + F(n - 2)$, perkalian vektor dan matriks yang mungkin adalah

$$ \begin{bmatrix} F(n) \\ F(n - 1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F(n - 1) \\ F(n - 2) \end{bmatrix} = \begin{bmatrix} F(n - 1) + F(n - 2) \\ F(n - 1) + 0 \end{bmatrix} $$

Vektor $v$ dan $v'$ masing-masing berisi berapa nilai pada rekurensi. Matriks $A$ bertujuan untuk menghitung nilai selanjutnya dan "menggeser" nilai rekurensi sebelumnya.

Kembali ke soal, rekurensi pada solusi awal mirip rekurensi Fibonacci, yaitu bergantung pada dua "kolom" sebelumnya. Bedanya, setiap kolom memiliki lima baris. Untuk memudahkan visualisasi, kita definisikian $g(n) = (f(1, n), f(2, n), ..., f(5, n))$ atau

$$g(n) = \begin{bmatrix} f(1, n) \\ f(2, n) \\ ... \\ f(5, n) \end{bmatrix}$$

Perkalian matriks yang mungkin adalah

$$ \begin{bmatrix} g(n) \\ g(n - 1) \end{bmatrix} = A \begin{bmatrix} g(n - 1) \\ g(n - 2) \end{bmatrix} $$

Misal $A$ direpresentasikan sebagai berikut $$A = \begin{bmatrix} a & b \\ c & d \end{bmatrix} $$

Jadi $$ \begin{bmatrix} g(n) \\ g(n - 1) \end{bmatrix} = \begin{bmatrix} a \cdot g(n - 1) + b \cdot g(n - 2) \\ c \cdot g(n - 1) + d \cdot g(n - 2) \end{bmatrix} $$

Jika kita anggap $g(n)$ sebagai vektor, maka $$g(n) = \begin{bmatrix} f(1, n) \\ f(2, n) \\ f(3, n) \\ f(4, n) \\ f(5, n) \end{bmatrix} = a\begin{bmatrix} f(1, n - 1) \\ f(2, n - 1) \\ f(3, n - 1) \\ f(4, n - 1) \\ f(5, n - 1) \end{bmatrix} + b\begin{bmatrix} f(1, n - 2) \\ f(2, n - 2) \\ f(3, n - 2) \\ f(4, n - 2) \\ f(5, n - 2) \end{bmatrix}$$

Struktur yang cocok untuk $a$ dan $b$ adalah matriks dengan ukuran 5 baris dan 5 kolom. Berdasarkan relasi rekurensi pada solusi awal, matriks $a$ dan $b$ yang memenuhi adalah

$$ a = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{bmatrix} $$ $$ b = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{bmatrix} $$

Sedangkan matriks $c$ dan $d$ sangat mudah ditentukan. Karena kita ingin "menyimpan" $g(n - 1)$ dan "menghilangkan" $g(n - 2)$, maka

$$ c = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} $$ $$ d = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} $$

Akhirnya, nilai dari matriks $A$ adalah sebagai berikut.

$$ A = \begin{bmatrix} \begin{bmatrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{bmatrix} & \begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{bmatrix} \\ \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} & \begin{bmatrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \end{bmatrix} $$

Untuk memudahkan implementasi, kita bisa mengubah matriks $A$ yang awalnya merupakan matriks di dalam matriks menjadi matriks berukuran 10 baris dan 10 kolom:

$$A = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}$$

Hal tersebut juga bisa dilakukan pada vektor $v$ dan $v'$. Contohnya, kasus dasar untuk solusi ini adalah

$$base = \begin{bmatrix} g(1) \\ g(0) \end{bmatrix} = \begin{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \\ \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$$

Jawaban dari soal ini adalah hasil penjumlahan elemen pada baris ke-1 sampai ke-5 pada vektor $v'$. Untuk mencarinya, perhatikan pola berikut.

  • Untuk $N = 1$ $$v' = \begin{bmatrix} g(1) \\ g(0) \end{bmatrix} = A^0 base $$
  • Untuk $N = 2$ $$v' = \begin{bmatrix} g(2) \\ g(1) \end{bmatrix} = A\begin{bmatrix} g(1) \\ g(0) \end{bmatrix} = A^1 base $$
  • Untuk $N = 3$ $$v' = \begin{bmatrix} g(3) \\ g(2) \end{bmatrix} = A\begin{bmatrix} g(2) \\ g(1) \end{bmatrix} = A(A^1 base) = A^2 base $$
  • Untuk $N = 4$ $$v' = \begin{bmatrix} g(4) \\ g(3) \end{bmatrix} = A\begin{bmatrix} g(3) \\ g(2) \end{bmatrix} = A(A^2 base) = A^3 base $$
  • ...

Terlihat bahwa untuk suatu $N$, maka $$v' = A^{N - 1} base$$

Pemangkatan matriks dapat dilakukan dengan teknik binary exponentiation untuk mempercepat eksekusinya. Kode akhir dapat dilihat pada bagian Kode.

Kode#

#include <iostream>
#include <cassert>
#include <vector>
using namespace std;
typedef long long int lli;

const int MOD = 1E9 + 7;

struct Matrix {
    int N, M;
    vector < vector <int> > entry;

    Matrix(int n, int m) : N(n), M(m) {
        entry.assign(n, vector <int>(m, 0));
    }

    Matrix operator*(const Matrix& other){
        assert(M == other.N);
        Matrix ret(N, other.M);
        for(int i = 0; i < N; i++){
            for(int j = 0; j < other.M; j++){
                for(int k = 0; k < M; k++){
                    ret.entry[i][j] += (lli)entry[i][k] * other.entry[k][j] % MOD;
                    ret.entry[i][j] %= MOD;
                }
            }
        }
        return ret;
    }

    Matrix operator^(int y){
        assert(N == M);
        Matrix ret(N, N);
        for(int i = 0; i < N; i++) ret.entry[i][i] = 1;

        Matrix x = *this;
        while(y){
            if(y & 1) ret = ret * x;
            x = x * x;
            y >>= 1;
        }
        return ret;
    }
};

int N;

int main(){
    cin >> N;

    Matrix A(10, 10);
    for(int i = 0; i < 3; i++) A.entry[i][i + 2] = A.entry[i + 2][i] = 1;
    for(int i = 0; i < 4; i++) A.entry[i][5 + i + 1] = A.entry[i + 1][5 + i] = 1;
    for(int i = 0; i < 5; i++) A.entry[5 + i][i] = 1;

    Matrix base(10, 1);
    for(int i = 0; i < 5; i++) base.entry[i][0] = 1;

    Matrix res = (A ^ (N - 1)) * base;

    int ans = 0;
    for(int i = 0; i < 5; i++) (ans += res.entry[i][0]) %= MOD;

    cout << ans << '\n';
    return 0;
}