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

general
, ,
1

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;
}
2

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
3

A few comments and better variable names would be appreciated.

4

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

1 Like
5

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

6

http://discuss.codechef.com/questions/2335/building-up-the-recurrence-matrix-to-compute-recurrences-in-ologn-time

Maybe this helps you!

2 Likes