## 10229 - Modular Fibonacci

Moderator: Board moderators

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 10229 - Modular Fibonacci

fR0D wrote:so how can i avoid that???
Use mod during each step of the computation.
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

shiv
New poster
Posts: 2
Joined: Mon May 02, 2011 9:53 pm

### Re: 10229 - Modular Fibonacci

i have tried this code of mine with all inputs/outputs (those posted on forum also)and it returned the correct answer, still this gives WA...please help..
#include<stdio.h>
#include<math.h>
long long M[2][2];
long long A[2][2];
long long C[2][2];

void matMul(long long n,long long m);
void mulM(long long m,long long n);

int main()
{
long long n,m;

while(scanf("%lld%lld",&n,&m)==2)
{

if(n==0){printf("0\n");continue;}
M[0][0]=1;M[0][1]=0;M[1][0]=0;M[1][1]=1;
A[0][0]=1;A[0][1]=1;A[1][0]=1;A[1][1]=0;
C[0][0]=0;C[0][1]=0;C[1][0]=0;C[1][1]=0;
m=pow(2,m);
matMul(n-1,m);

printf("%lld\n",M[0][0]);

}
return(0);
}

void matMul(long long n,long long m)
{
if(n>1)
{
matMul(n/2,m);
mulM(0,m);
}
if(n%2!=0)
{
mulM(1,m);
}
}

void mulM(long long m,long long n)
{
int i,j,k;

if(m==0)
{

for(i=0;i<2;i++)
for(j=0;j<2;j++)
{
C[j]=0;
for(k=0;k<2;k++)

C[j]=(C[j]%n)+((((M[k]%n)*(M[k][j]%n))%n)%n);
}
}
else
{

for(i=0;i<2;i++)
for(j=0;j<2;j++)
{
C[j]=0;
for(k=0;k<2;k++)
C[j]=(C[j]%n)+((((A[k]%n)*(M[k][j]%n))%n)%n);
}
}

for(i=0;i<2;i++)
for(j=0;j<2;j++)
{
M[j]=C[j];
}
}

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 10229 - Modular Fibonacci

Its the 1st problem i solved on matrix exponentiation. To learn it,read this fine tutorial: http://zobayer.blogspot.com/search/labe ... nentiation.

Dont forget to use long long as intermediate calculation can cross int limit.

@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

### Re: 10229 - Modular Fibonacci

Getting WA...plzz help...

Code: Select all

Code Removed. AC:)
Last edited by @ce on Wed Jun 12, 2013 5:11 am, edited 2 times in total.
-@ce

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10229 - Modular Fibonacci

Did you mean to type 128.256 on line 19?
Check input and AC output for thousands of problems on uDebug!

@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

### Re: 10229 - Modular Fibonacci

Thanks brianfry.
-@ce

triplemzim
New poster
Posts: 48
Joined: Sat Apr 06, 2013 6:02 pm

### Re: 10229 - Modular Fibonacci

Shafaet_du wrote:Its the 1st problem i solved on matrix exponentiation. To learn it,read this fine tutorial: http://zobayer.blogspot.com/search/labe ... nentiation.

Dont forget to use long long as intermediate calculation can cross int limit.

it is also my first problem... on Matrix exponentiation. Nice tutorial ...

nazmul225
New poster
Posts: 1
Joined: Mon May 26, 2014 2:13 pm

### Re: 10229 - Modular Fibonacci

why wa?

Code: Select all

#include<bits/stdc++.h>
#define i64 long long
#define filein freopen("in.txt","r",stdin)
#define fileout freopen("my.txt","w",stdout)

using namespace std;

void multiply(i64 F[2][2], i64 M[2][2]){
i64 x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];
i64 y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];
i64 z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];
i64 w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];

F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}

void power(i64 F[2][2], i64 n){
if( n == 0 || n == 1)
return;
i64 M[2][2] = {{1,1},{1,0}};

power(F, n/2);
multiply(F, F);

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

i64 fib(i64 n){
i64 F[2][2] = {{1,1},{1,0}};
if (n == 0)
return 0;
power(F, n-1);
return F[0][0];
}

int main()
{
i64 n, m;
while(scanf("%lld %lld",&n,&m) == 2){
i64 f = fib(n);
i64 mod = pow(2,m);
i64 ans = f % mod;
printf("%lld\n",ans);
}
return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10229 - Modular Fibonacci

Try replacing:
pow(2, m)
with:
1LL << m
Check input and AC output for thousands of problems on uDebug!