Module: hızlı üs alma


Problem

4/5

**Fibonacci sayıları modulo (C++)

Theory Click to read/hide

Modulo Fibonacci sayıları

Fibonacci sayısını verimli bir şekilde bulmak için matris çarpımını kullanıyoruz, daha fazla ayrıntı buradan.
 
Bunu bilmek 
\(F_{n+m} = F_m F_{n+1} + F_{m-1} F_n\), tekrar ilişkisini yaz matris çarpımı için:
&boğa; \(m = n\) ise \(F_{2n} = F_n F_{n+1} + F_ { n-1} F_n\);
&boğa; \(m = n + 1\) ise \(F_{2n+1} = F_{n+1 } F_{n+1} + F_n F_n\).
 

Problem

Bildiğiniz gibi Fibonacci dizisi şu şekilde tanımlanır:
\(F(0) = 0,\ F(1) = 1,\ F(n) = F(n – 1) + F(n – 2)\ ), tüm \(n > 1\) için.
Adını Pisalı Leonardo olarak da bilinen İtalyan matematikçi Leonardo Fibonacci'den almıştır.
 
Giriş
Dize bir tamsayı içerir n (\(1 <= n <= 10^{18}\)).
 
Çıktı
F(n) değerini, hesaplanan modulo \(10^8\) yazdırın.

Eksik kod parçacığını programa yapıştırın.

 

Örnekler

 

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
# Girdi Çıktı
1 30 832040
Write the program below 
#include <iostream>
#include <map>

using namespace std;

#define MOD 100000000

map<long, long> F;

long fib(long n)
{       
}

long a;

int main()
{
	
	cin >> a;
	cout << fib(a);
	return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!