You are not logged in. Please login at www.codechef.com to post your questions!

×

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

asked 30 Mar '14, 14:29

ac_c0der's gravatar image

2★ac_c0der
72448
accept rate: 0%

A few comments and better variable names would be appreciated.

(30 Mar '14, 15:31) kcahdog3★
1

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

(30 Mar '14, 15:41) subway5★

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;

link

answered 30 Mar '14, 15:54

bulatov's gravatar image

5★bulatov
1263
accept rate: 50%

edited 30 Mar '14, 15:59

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

(30 Mar '14, 16:19) ac_c0der2★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,455
×166
×107

question asked: 30 Mar '14, 14:29

question was seen: 5,848 times

last updated: 30 Mar '14, 16:25