SPOJ FIBOSUM WA

general
1

#include<stdio.h>

long long f[2][2];
long long fb[2][2];
long long mod = 1000000007;

void solve(long long n)
{

    if(n == 0){
        f[0][0] = 1;
        f[0][1] = 0;
        return;
    }

    if(n == 1){
        f[0][0] = 1;
        f[0][1] = 1;
        f[1][0] = 1;
        f[1][1] = 0;
        return;
    }

    if(n%2 == 1){
        solve(n/2);
        multiply(f,f);
        multiply(f,fb);
    }
    else{
        solve(n/2);
        multiply(f,f);
    }

}

void multiply(long long ff[2][2],long long m[2][2])
{

    long long x = (ff[0][0] * m[0][0]) + (ff[0][1] * m[1][0]);
    long long y = (ff[0][0] * m[0][1]) + (ff[0][1] * m[1][1]);
    long long w = (ff[1][0] * m[0][0] )+ (ff[1][1] * m[1][0]);
    long long z = (ff[1][0] * m[0][1]) + (ff[1][1] * m[1][1]);
    /*printf("Multiplying %lld %lld %lld %lld \n",x,y,w,z);*/
    f[0][0] = x;
    f[0][1] = y;
    f[1][0] = w;
    f[1][1] = z;

}

int main()
{
    int t;
    long long n,m;
    long long a,b,c,sum;

    fb[0][0] = 1;
    fb[0][1] = 1;
    fb[1][0] = 1;
    fb[1][1] = 0;

    scanf("%d",&t);

    while(t--){

        scanf("%lld %lld",&n,&m);

        if(n == m){
            solve(n);
            a = f[0][1];
            a = a % mod;
            printf("%lld\n",a);
            continue;
        }
        solve(n+1);

        a = f[0][1] - 1;

        solve(m+2);

        b = f[0][1] -1;

        sum = (b - a) % mod;

        printf("%lld\n",sum);

    }
    return 0;
}

I am not getting what is the error in the above code. I have read that there could be an underflow but how can it happen in my code? And if does happen how to resolve it? If underflow is not there why am i getting WA?

2

You need the refresh the fb and f arrays and change the formula from this

sum=(b-a)%MOD to sum=(b-a+MOD)%MOD

3

It’s not working. Please help!