Page 4 of 4
Re: 10229 - Modular Fibonacci
Posted: Sun Apr 24, 2011 3:48 am
by DD
fR0D wrote:so how can i avoid that???
Use mod during each step of the computation.
Re: 10229 - Modular Fibonacci
Posted: Mon May 02, 2011 10:12 pm
by shiv
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];
}
}
Re: 10229 - Modular Fibonacci
Posted: Fri May 20, 2011 4:52 pm
by Shafaet_du
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.
Re: 10229 - Modular Fibonacci
Posted: Tue Jun 11, 2013 7:25 am
by @ce
Getting WA...plzz help...
Re: 10229 - Modular Fibonacci
Posted: Wed Jun 12, 2013 1:01 am
by brianfry713
Did you mean to type 128.256 on line 19?
Re: 10229 - Modular Fibonacci
Posted: Fri Jun 21, 2013 9:12 pm
by @ce
Thanks brianfry.
Re: 10229 - Modular Fibonacci
Posted: Wed Oct 30, 2013 1:14 pm
by triplemzim
it is also my first problem... on Matrix exponentiation. Nice tutorial ...
Re: 10229 - Modular Fibonacci
Posted: Sun Jan 11, 2015 10:41 pm
by nazmul225
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;
}
Re: 10229 - Modular Fibonacci
Posted: Tue Jan 13, 2015 2:16 am
by brianfry713
Try replacing:
pow(2, m)
with:
1LL << m