Matrix Exponentiation - Knight Paths

Xem dạng PDF
Gửi bài giải
Điểm: 0,80
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Người đăng:
bachlamsung123
Nguồn bài:
Matrix Exponentiation
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một quân mã được đặt ở ô trái trên của bàn cờ kích thước ~8 \times 8~. Bạn được phép di chuyển quân mã đó tối đa ~k~ lần. Hãy đếm số đường đi có thể có với quân mã đó và in ra kết quả dưới dạng modulo cho ~2^{32}~.

Cụ thể hơn, một đường đi là một tập các ô ~(C_1, C_2,..., C_s)~ sao cho ~1 \le s \le k + 1~ và quân mã có thể đi từ ô ~C_i~ đến ô ~C_{i+1}~ với mọi ~i~.

(Một nước đi của quân mã trong bàn cờ vua có dạng ~1~ ô vuông theo chiều ngang và ~2~ ô vuông theo chiều dọc hoặc ~2~ ô vuông theo chiều ngang và ~1~ ô vuông theo chiều dọc)

Input

Số nguyên ~k~ ~(0 \le k \le 10^9)~

Output

In ra kết quả dưới dạng modulo cho ~2^{32} = 4294967296 ~

Sample 1

Input
1
Output
3

Sample 2

Input
2
Output
15

Sample 3

Input
6
Output
17231

Giải thích Sample 1

Quân mã có thể đứng nguyên ở ô ~(1, 1)~ hoặc có thể di chuyển tới các ô ~(2, 3)~ hoặc ~(3, 2)~. Vậy kết quả là ~3~.

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • -3
    phannam310810  đã bình luận lúc 12, Tháng 11, 2025, 9:21

    include <bits/stdc++.h>

    using namespace std;

    define int long long

    define endl '\n'

    define ull unsigned long long

    const int mod = 4294967296; struct Matrix{ vector data; Matrix(int n = 0, int m = 0) : data(n, vector<int>(m, 0)) {}

    int row() {return data.size();}
int col() {return data[0].size();}

auto & operator [](int id) {return data[id];}

friend ostream & operator << (ostream &out, const Matrix &res){
    for(auto x : res.data){
        for(auto y : x){
            out << y << " ";
        }
        out << endl;
    }
    return out;
}

    }; Matrix I(int n){ Matrix res(n, n); while(n){ res[n - 1][n - 1] = 1; n--; } return res; } Matrix operator * (Matrix A, Matrix B){ Matrix res(A.row(), B.col()); for(int i = 0; i < A.row(); i++){ for(int j = 0; j < B.col(); j++){ for(int k = 0; k < A.col(); k++){ res[i][j] = ((ull)res[i][j] + A[i][k] * B[k][j]) % mod; } } } return res; } Matrix operator + (Matrix A, Matrix B){ Matrix res(A.row(), B.col()); for(int i = 0 ; i < A.row(); i++){ for(int j = 0; j < B.col(); j++){ res[i][j] = ((ull)A[i][j] + B[i][j]) % mod; } } return res; } Matrix binpow(Matrix A, int k){ Matrix sum(A.row(), A.row()); Matrix res = I(A.row()); Matrix S = I(A.row()); while(k){ if(k & 1){ sum = sum + (S * res); res = res * A; } S = S + (S * A); A = A * A; k >>= 1; } return sum; } int dx[] = {2, 2, -2, -2, 1, 1, -1, -1}; int dy[] = {1, -1, 1, -1, 2, -2, 2, -2}; void solve(){ int n; cin >> n; Matrix A(64, 64), dp(64, 1); for(int x = 0; x < 8; x++){ for(int y = 0; y < 8; y ++){ for(int i = 0; i < 8; i++){ int nx = dx[i] + x; int ny = dy[i] + y; //cout << nx * 8 + ny << endl << x * 8 + y << endl; int to = nx * 8 + ny, from = x * 8 + y;

                if(nx >= 0 && nx < 8 && ny >= 0 && ny < 8) A[to][from] = 1;
        }
    }
}
//cout << A << endl;
dp[0][0] = 1;
A = binpow(A, n + 1);
dp = A * dp;
int ans = 0;
for(int i = 0; i < 64; i++){
    ans = (ans + dp[i][0]) % mod;
}
cout << ans;

    } signed main() { if(fopen("input.txt", "r")) freopen("input.txt", "r", stdin); iosbase::syncwith_stdio(false); cin.tie(nullptr); solve(); return 0; }

    Chep di moi nguoi