Module: الأس السريع


Problem

4/5

** نموذج أرقام فيبوناتشي (C ++)

Theory Click to read/hide

أرقام مودولو فيبوناتشي للعثور على رقم فيبوناتشي بكفاءة ، نستخدم ضرب المصفوفة ، مزيد من التفاصيل هنا .
نبسب ؛
مع العلم أن نبسب؛
\ (F_ {n + m} = F_m F_ {n + 1} + F_ {m-1} F_n \) ، & nbsp؛ اكتب علاقة التكرار لمنتج المصفوفة:
& الثور؛ إذا \ (m = n \) ثم \ (F_ {2n} = F_n F_ {n + 1} + F_ { n-1} F_n \) ؛
& الثور؛ إذا \ (m = n + 1 \) ثم \ (F_ {2n + 1} = F_ {n + 1} F_ {n + 1} + F_n F_n \) .
& nbsp؛

Problem

كما تعلم ، يتم تعريف تسلسل فيبوناتشي على النحو التالي:
\ (F (0) = 0، \ F (1) = 1، \ F (n) = F (n - 1) + F (n - 2) \ ) ، لجميع \ (n & gt؛ 1 \) .
تمت تسميته على اسم عالم الرياضيات الإيطالي ليوناردو فيبوناتشي ، المعروف أيضًا باسم ليوناردو بيزا.
& nbsp؛
إدخال
تحتوي السلسلة على عدد صحيح n ( \ (1 & lt؛ = n & lt؛ = 10 ^ {18} \) ).
& nbsp؛
الإخراج
طباعة قيمة F (n) ، & nbsp ؛ modulo المحسوب \ (10 ​​^ 8 \) .

الصق مقتطف الشفرة المفقود في البرنامج.

أمثلة <الجسم>
# إدخال الإخراج
1 30 832040

نبسب ؛

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++
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!