LATGACH4 – spoj

Đề bài:

Thuật toán:

    Gọi f[i] là số cách xếp gạch
    dùng viên gạch 1×2 => f[i] = f[i – 2];
    dùng viên gạch 2×2 => f[i] = f[i – 1];
    => f[i] = f[i – 1] + f[i – 2];
    Do n quá lớn nên mình có thể dùng nhân ma trận tốn O(log2(n))

Code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 111539786;
 
map <ll, ll> f;
 
ll get(ll n)
{
    if (f.count(n)) return f[n];
    ll k=n / 2;
    if (!(n % 2))
        return f[n]=(get(k)*get(k) + get(k-1)*get(k-1)) % mod;
    else
        return f[n]=(get(k)*get(k+1) + get(k-1)*get(k)) % mod;
}
main()
{
    int t, n;
    cin>>t;
    while (t--)
    {
        cin>>n;
        f[0]=f[1]=1;
        cout<<get(n)<<endl;
    }
}
Khuyên dùng

 

Speak Your Mind

*