I’m trying to solve FIBHARD from spoj. Here N goes very high. My first thought was that Euler totient function will work but doesn’t seems to be working. Any suggestion how to deal with such a large N. @vijju123 @galencolin @everule1
3 Likes
Will matrix exponentation work?
check N, how it will work? I have no idea, If you had any please share.
Matrix exponentation is of O(lgn). Btw fibonacci series has formula Fn = {[(√5 + 1)/2] ^ n} / √5
Please check N. Maybe we need to apply some maths on N. After that we can use some other technique. I think provided N neither suitable for Binet’s formula, nor for matrix expo.
Though i tried with this formula in python, It doen’t work.
On codeforces, there is a blog for calculating fib(n) for 10^18, but that’s not enough for this problem.
I think there is something to do with modulo 998244353 and FFT for this problem.
I hope, it will be useful to you.
1 Like
Maybe this is correct solution. I had no idea what FFT is.
Fibonacci Numbers - Algorithms for Competitive Programming.
Have a look This might help.
This is still not the complete solution(we have to still find the period of the function)
1 Like
Maybe you are right, but at present i’m trying to figure out what the heck is FFT.
This code is giving the desired output having input as large as 10^18.
You still need to read the large value of n and convert that into
long req = (n-1)%(mod*mod-1);
Here, req is < 10^18, so it wont be a problem, once req is obtained correctly from n.
#include <map>
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define long long long
const long M = 998244353; // modulo
map<long, long> F;
long f(long n) {
if (F.count(n)) return F[n];
long k=n/2;
if (n%2==0) { // n=2*k
return F[n] = (f(k)*f(k) + f(k-1)*f(k-1)) % M;
} else { // n=2*k+1
return F[n] = (f(k)*f(k+1) + f(k-1)*f(k)) % M;
}
}
main(){
long n;
F[0]=F[1]=1;
while (cin >> n) {
long req = (n-1)%(M*M-1); // get req correct for large values of n
cout << (n==0 ? 0 : f(req)) << endl;
}
}
I used this article from codeforces and the comment of this question to arrive to this solution.
We can use fast doubling method using the formulas:
For nth Fibonacci, if n is :-
Even -> F(2k) = F(k)[2F(k+1)-F(k)]
Odd -> F(2k+1) = F(k+1)*F(k+1) + F(k)*F(k)
Also using BigInteger and modular arithmetic as well.
What about using the fact that the Fibonacci sequence modulo p is periodic? If you find the period, let’s call it P, then you just need to calculate the (N%P)-th term. P is always smaller than p^2 + 1.
[EDIT] I just submited this approach and worked. I couldn’t figure out a fast way to find P so I did an offline brute force search.
2 Likes
Yeah buddy i know last digit is repeating after 60 'th term similarly last two digits repeat after 300 terms , last three digit is repeating after 1500 terms and so on but how i will find period for mod m ?
As I said, I did it locally (offline) and then used it in my submition.
Brute Force
const unsigned int MOD=998244353;
unsigned int a=1,b=1;
long long P=1;
while (a!=0 || b!=1){
ui tmp=a;
a=b;
b += tmp;
if (b>=MOD) b-=MOD;
++P;
}
The value of P I found was 1996488708
3 Likes
Yeah same 
Thanks (actually i forgot this is called Pisano Period )
1 Like
Good to know, I hadn’t heard of that before. Anyway, I will almost certainly forget this by tomorrow 
Lmao … There is no need to learn the name , u know algorithm and that’s enough 
BTW here is my code It will give TLE …how can i optimize ?
TLE_CODE
the N%P in your code has many % operations, you can reduce that. There’s many resources of bigint clases implementations that you can check. Most of them have a definition of modulus operation.
Once you have found N%P you calculate the fibo of that number using a log(N%P) approach: matrix exponentiation or fast doubling.
1 Like