Module: तेज घातांक


Problem

4/5

** फाइबोनैचि संख्या सापेक्ष (C++)

Theory Click to read/hide

मॉड्यूलो फाइबोनैचि संख्याएं

फाइबोनैचि संख्या को प्रभावी ढंग से खोजने के लिए, हम मैट्रिक्स गुणन का उपयोग करते हैं, अधिक विवरण यहां।
 
यह जानकर 
\(F_{n+m} = F_m F_{n+1} + F_{m-1} F_n\), पुनरावृत्ति संबंध लिखें मैट्रिक्स उत्पाद के लिए:
• अगर \(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\)।
 

Problem

जैसा कि आप जानते हैं, फाइबोनैचि अनुक्रम को इस प्रकार परिभाषित किया गया है:
\(F(0) = 0,\ F(1) = 1,\ F(n) = F(n – 1) + F(n – 2)\ ), सभी \(n > 1\) के लिए।
इसका नाम इतालवी गणितज्ञ लियोनार्डो फिबोनाची के नाम पर रखा गया है, जिसे पीसा के लियोनार्डो के नाम से भी जाना जाता है।
 
इनपुट
स्ट्रिंग में एक पूर्णांक n (\(1 <= n <= 10^{18}\)) है।
 
आउटपुट
प्रिंट करें F(n) मान, परिकलित मोडुलो \(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!