# calculate f(n) = a*f(n-1) + b*f(n-2) matrix exponentiation

Given f(1)=1 , f(2)=1 , and f(n) = 100*f(n-1)+200f(n-2) .
Now , i have to calculate f(n) rof n upto 10^9 , so obvious approach id to use matrix exponentiation …
I came up with this logic , but it gives wrong output . Can you please explain the reason ?
It fails with n=3 , but i am not able to come up with how to resolve it .

``````#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll m=1000000007;
ll x,y,z,w;
void ml(ll F[2][2],ll M[2][2])
{
x =  ((F[0][0]%m)*(M[0][0]%m))%m + ((F[0][1]%m)*(M[1][0]%m))%m;
y =  ((F[0][0]%m)*(M[0][1]%m))%m + ((F[0][1]%m)*(M[1][1]%m))%m;
z =  ((F[1][0]%m)*(M[0][0]%m))%m + ((F[1][1]%m)*(M[1][0]%m))%m;
w =  ((F[1][0]%m)*(M[0][1]%m))%m + ((F[1][1]%m)*(M[1][1]%m))%m;

F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
//cout<<F[0][0]<<" " <<F[0][1]<<" "<< F[1][0]<<" " <<F[1][1]<<endl;
}

void po(ll F[2][2],ll n)
{
if( n<=1)
return;

ll M[2][2] = {{100,200},{1,0}};

po(F,n/2);
ml(F,F);

if( n%2 != 0 )
ml(F,M);
}

ll f(ll n)
{
ll F[2][2] = {{100,200},{1,0}};

if(n<=2)
return 1;
po(F,n-1);
return F[0][0];
}

int main(){

freopen("input.txt", "rt", stdin);
ll ans,n;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%llu",&n);
ans=f(n);

printf("%llu\n",ans);
}
return 0;
}``````

Use this matrix for F and M:

100 1

200 0

To get result matrix for n you need (n - 2) power of F.

And answer is: (F[0][0] + F[1][0]) % m;

1 Like

A few comments and better variable names would be appreciated.

this question is similar to one from an ongoing contest at hackerearth .I would request the admin to temporarily close the question.

1 Like

please explain it also , i want to learn how to find it .

2 Likes