can anyone explain this sollution especially the fib part.
here’s the sollution to DSA learning series contest 6 QUESTION 4.
#include <bits/stdc++.h>
using namespace std;
void power(long long int F[2][2],long long int n);
void multiply(long long int F[2][2],long long int M[2][2]);
const long long int MOD = 1000000007;
long long int fib(long long int n)
{
long long int F[2][2] = {{1,1},{1,0}};
if (n == 0)
return 0;
power(F, n-1);
return F[0][0];
}
void power(long long int F[2][2],long long int n)
{
if( n == 0 || n == 1)
return;
long long int M[2][2] = {{1,1},{1,0}};
power(F, n/2);
multiply(F, F);
if (n%2 != 0)
multiply(F, M);
}
void multiply(long long int F[2][2],long long int M[2][2])
{
long long int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
long long int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
long long int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
long long int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];
F[0][0] = x%MOD;
F[0][1] = y%MOD;
F[1][0] = z%MOD;
F[1][1] = w%MOD;
}
int main()
{
long int t;long long int n,k;
scanf("%ld",&t);
while(t>0){
scanf("%lld%lld",&n,&k);
int x = n/k;long long int ans = 0;x %= 1000000007;
long long int y = n%k;
if(x>0){
ans+= ((x * (fib(k+1) - 1))%1000000007);
//ans %= 1000000007;
}
if(y > 0){
ans+= (fib(y+1) - 1);
ans %= 1000000007;
}
printf("%lld\n",ans);
t–;
}
return 0;
}