Processing math: 50%
Solutions of Fibonacci 2 - MarisaOJ: Marisa Online Judge

Solutions of Fibonacci 2

Select solution language

Write solution here.


User Avatar NguyenKhangNinh_99    Created at    3 likes

Chúng ta có thể sử dụng khử nhân ma trận (Tham khảo thêm ở blog này: https://codeforces.com/blog/entry/14516) Code mẫu: `cpp #include <bits/stdc++.h> using namespace std; #define int long long const int mod = 1e9 + 7; map<int, int> fibo; int recur(int n) { if (fibo.count(n)) return fibo[n]; int k = n / 2; if (n & 1) return fibo[n] = (recur(k) * recur(k + 1) + recur(k - 1) * recur(k)) % mod; else return fibo[n] = (recur(k) * recur(k) + recur(k - 1) * recur(k - 1)) % mod; } signed main(){ int n; cin >> n; fibo[0] = fibo[1] = 1; cout << (n == 0 ? 0 : recur(n-1)); }

User Avatar MQuang    Created at    2 likes

Code mẫu (Hãy code thử trước khi xem): #clude<bitsstdc++.h>usingnamespacestd;#defelonglong#defeir<r<#defeFOR(i,a,b)for(i=a;i<()b;i++)constMOD=1e9+7;voput(){#defetasknamemainif