10229 - Modular Fibonacci

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

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

Post by DD » Sun Apr 24, 2011 3:48 am

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

Post by shiv » Mon May 02, 2011 10:12 pm

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
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10229 - Modular Fibonacci

Post by Shafaet_du » Fri May 20, 2011 4:52 pm

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.

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

Re: 10229 - Modular Fibonacci

Post by @ce » Tue Jun 11, 2013 7:25 am

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

Post by brianfry713 » Wed Jun 12, 2013 1:01 am

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

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

Re: 10229 - Modular Fibonacci

Post by @ce » Fri Jun 21, 2013 9:12 pm

Thanks brianfry.
-@ce

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

Re: 10229 - Modular Fibonacci

Post by triplemzim » Wed Oct 30, 2013 1:14 pm

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

Post by nazmul225 » Sun Jan 11, 2015 10:41 pm

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

Post by brianfry713 » Tue Jan 13, 2015 2:16 am

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

Post Reply

Return to “Volume 102 (10200-10299)”