10229 - Modular Fibonacci

[DD]

so how can i avoid that???

Use mod during each step of the computation.

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

[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.

[@ce]

Getting WA...plzz help...

Code: Select all

Code Removed. AC:)

[brianfry713]

Did you mean to type 128.256 on line 19?

[@ce]

Thanks brianfry.

[triplemzim]

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]

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]

Try replacing:
pow(2, m)
with:
1LL << m