Fibonacci numbers with help of DP

                                                    Hard Fibonacii......

Today we eill learn to find the n'th fibonacci number after %M.

Since it is vey dfficult to store the large Fibonacci number,because the rate is exponention.

But there is a unique properties of Fibonacci series by which it is periodic n nature....

Lets see an samll example

 m = 2 or m = 3.

Take a detailed look at this table. Do you see? Both these sequences are periodic!
 For m = 2, the period is 011 and has length 3, while for
 m = 3 the period is 01120221 and has length 8.
 Therefore, to compute, say, F2015 mod 3 we just need to find the remainder of 2015 when divided by 8. Since 2015 = 251·8 + 7, we conclude that F2015 mod 3 = F7 mod 3 = 1. This is true in general: for any integer m ≥ 2, the sequence Fn mod m is periodic. The period always starts with 01 and is known as Pisano period.

Here is the complete code for the above problem.

#include<bits/stdc++.h>
using namespace std;
long long int arr[1000001];
int calculate(long long int N,long long int M)
{
    arr[0]=0;
    arr[1]=1;
    arr[2]=1;
    long long int prev=0,curr=1,temp;
    for(int i=2;i<=N;i++)
    {
        arr[i]=(prev+curr)%M;
        if(arr[i]==1 && arr[i-1]==0)
        {
            return i-1;
        }
        temp=curr;
        curr=(prev+curr)%M;
        prev=temp;
    }
}
long long ans(long long int N,long long int M)
{
    long long int i=calculate(N,M);
    return arr[N%i];
}
int main()
{
    long long int N,M;
    cin>>N>>M;
    cout<<ans(N,M);
}