Lát gạch 4

View as PDF
Submit solution
Points: 0.05 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
Thầy Ðỗ Ðức Ðông
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một hình chữ nhật kích thước ~2 \times N~ (~1 \le N < 10^{9}~). Hãy đếm số cách lát các viên gạch nhỏ kích thước ~1 \times 2~ và ~2 \times 1~ vào hình trên sao cho không có phần nào của các viên gạch nhỏ thừa ra ngoài, cũng không có vùng diện tích nào của hình chữ nhật không được lát.

Input

Gồm nhiều test, dòng đầu ghi số lượng test ~T~ ( ~T \le 100~ ). ~T~ dòng sau mỗi dòng ghi một số ~N~.

Output

Ghi ra ~T~ dòng là số cách lát tương ứng lấy phần dư cho ~111\,539\,786~.

Sample Input

3
1
2
3

Sample Output

1
2
3

Comments

Please read the guidelines before commenting.


  • 0
    Vohongtribao183  commented on April 29, 2026, 9:10 a.m.

    mình thấy nhân ma trận một khi đã hiểu thì áp dụng khá là dễ, quan trọng nhất vẫn là tư duy của mình để ra được công thức dp th ;-;


  • 1
    vominhmanh10  commented on Jan. 6, 2026, 12:15 p.m. ← edited

    sao thấy nhân ma trận ngta dài không biết có thêm gì không nx

    #include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define IO ios::sync_with_stdio(0); cin.tie(0)
const ll maxn = 1e6 + 5, inf = 1e18, mod = 111539786;
const vector<vector<ll>> I = {{1, 0}, {0, 1}};
ll t, n;
vector<vector<ll>> fi = {{1, 1}, {1, 0}}, d = {{1, 1}}; 
vector<vector<ll>> nhan_ma_tran(vector<vector<ll>> &a, vector<vector<ll>> &b) {
    ll n = a.size(), m = b[0].size();
    vector<vector<ll>> c(n, vector<ll>(m));
    for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % mod;
    return c;
}
vector<vector<ll>> power(vector<vector<ll>> &a, ll b) {
    if (!b) return I;
    vector<vector<ll>> x = power(a, b / 2), y;
    if (b & 1) {
        y = nhan_ma_tran(x, a);
        return nhan_ma_tran(y, x);
    }
    return nhan_ma_tran(x, x);
}
int main() {
    IO; cin >> t;
    while (t--) {
        cin >> n;
        vector<vector<ll>> x = power(fi, n - 1);
        cout << nhan_ma_tran(d, x)[0][0] % mod << "\n";
    }
}

  • -19
    chunguyen2k8  commented on Feb. 20, 2024, 12:12 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -11
    khieudung123  commented on Aug. 29, 2023, 3:10 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 2
    trongtenlinhcbhk64  commented on May 16, 2023, 8:46 a.m.

    bài hay quá =))


  • -31
    loingu1902  commented on Oct. 18, 2022, 7:19 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -85
    nngovannhhungg  commented on Jan. 15, 2022, 8:11 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.