ECODOWN - Editorial

editorial
, , , ,
1

Problem Link : CodeChef: Practical coding for everyone

Using Basic Mathematics, equation can be converted as :

F(x) = F(x-1) + F(x-2) + F(x-1)*F(x-2)

F(x) = F(x-1) + F(x-2) + F(x-1)*F(x-2) + 1 – 1

F(x) = ( F(x-1) + 1 ) * (F(x-2) + 1 ) - 1

F(x) + 1 = ( F(x-1) + 1 ) * (F(x-2) + 1 )

Let G(x) = F(x) + 1

G(x) = G(x-1) * G(x-2)

Now in question F(0) = a , F(1) = b;

G(0) = a + 1

G(1) = b + 1

G(2) = (a + 1)*(b + 1)

G(3) = (G(2) * G(1)) = (a + 1)(b + 1)(b + 1)

G(4) = ((a + 1)^2) * ((b + 1)^3)

G(5) = ((a + 1)^3) * ((b + 1)^5)

On observation,

for any k, G(k) = ((a + 1)^( (Kth – 1) fibonaci number)) * ((b + 1)^(Kth fibonaci number)

Now the question reduces to calculate the power of a number

Since the bibonaci number is very large, Even the 100th fibonaci numbe has 21 digits so we cant the the fibonaci number

We have heard about fermat little theorem,

It states that

(a^(p-1) ) % p = 1 where p is a prime number

From quotient remainder theorem:

fib( n ) = k * (p-1) + (fib(n) % (p – 1))

Now using this :

( c^( fib(n) ) ) % p = ( c^((k)*(p-1)) ) % p * ( c ^ (fib(n) % (p – 1))) % p

can be written as : X = Y * Z

Z can be easily calculated as (fib(n) % (p – 1)) can be easily store in int datatype

Y = 1 using fermat therorem

Nth fibo num can be calculated using Matrix Exponentaion.

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD 1000000007


ll power(ll a, ll b){
    if(b == 0){
        return 1;
    }
    ll temp = power(a, b/2);
    temp = (temp*temp)%MOD;
    if(b % 2 != 0){
        temp = temp * a;
    }
    return temp%MOD;
}


// matrix expo to calculate nth fibo in log n time
ll fib(ll n){
    if(n == 0 || n == 1 || n == 5){
        return n;
    }
    if(n == 2){
        return 1;
    }
    n = n - 1;
    ll a[2][2] = {1,1,1,0};
    ll ans[2][2] = {1,0,0,1};
    ll temp[2][2];
    ll mod = MOD-1, i , j , k;
    while(n){
        if(n % 2 != 0){
            for(i = 0; i < 2; i++){
                for(j = 0; j < 2; j++){
                    temp[i][j] = 0;
                    for(k = 0 ; k < 2; k++){
                        temp[i][j] += a[i][k] * ans[k][j];
                        temp[i][j] %= mod;
                    }
                }
            }
            for (i = 0; i < 2; i++)
            {
                for (j = 0; j < 2; j++)
                {
                    ans[i][j] = temp[i][j];
                }
            }
        }
        for(i = 0; i < 2; i++){
            for(j = 0; j < 2; j++){
                temp[i][j] = 0;
                for(k = 0; k < 2; k++){
                    temp[i][j] += a[i][k]*a[k][j];
                    temp[i][j] %= mod;
                }
            }
        }
        for(i = 0 ; i < 2; i++){
            for(j = 0; j < 2; j++){
                a[i][j] = temp[i][j];
            }
        }
        n >>= 1;
    }
    return ans[0][0];

}
int main(){
    ll test;
    cin >> test;
    while(test--){
        ll a, b, n, c;
        cin >> a >> b >> n;
        if(n == 0){
            cout << a << endl;
        }
        else if( n == 1){
            cout << b << endl;
        }
        else{
            ll x = fib(n-1);
            ll y = fib(n);
            c = power(a+1, x)* power(b+1, y);
            c--;
            c = c%MOD;
            c = (c + MOD)%MOD;
            cout << c << endl;
            
        }

    }
    return 0;
}
5 Likes
2

hello, could you help me to find out why I am getting TLE it looks good to me. I am using matrix Exponentiation
https://www.codechef.com/viewsolution/31890875

3

Your code is correct, but the implementation is slow.
There are two ways to fix it. Either do one matrix expo and calculate both fib(n-1) and fib(n-2) or precalculate \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{2^n}.
I calculated them both together and you can see the implementation here.
https://www.codechef.com/viewsolution/31891149

Also, you are using too many modulo operations.
I tried optimising it but it’s still not fast enough.
https://www.codechef.com/viewsolution/31891224

1 Like
4

I just submitted a code which compute both fib at once but still getting TLE
https://www.codechef.com/viewsolution/31891335

5

https://www.codechef.com/viewsolution/31891359
I optimised it. It does the same, but has a much better constant term.
You can use my matrix struct instead, it’s fast enough and easy to use.

1 Like
6

could you please elaborate a bit more why this is happening and how by changing return type to inline it got accepted.

7

All that’s not necessary, I was trying to figure out how to optimise it. Just declaring L and M as const will do the trick

4 Likes
8

Thank you so much just one last doubt. by matrix struct do you mean if I construct a class/struct for matrix and all its operations like multiplication, power It would have run faster?

9

You can code faster, that’s the point. If you want speed, then arrays and exponentiating in the solve function will be fastest because minimal construction is needed. Also It’s optimised enough already.

2 Likes
10

I have seen the similar question in CodeSule Feb 2019 here

Screenshot_2020-04-15-10-43-56-009_com.android.chrome
Screenshot_2020-04-15-10-43-56-009_com.android.chrome1080×2280 308 KB

1 Like
11 
#include <bits/stdc++.h>
using namespace std;
#define test int t;cin >> t;while(t--)
long long MOD = 1000000000 + 7;
struct matrix2X2{
    long long a,b,c,d;
};
matrix2X2 matrixProduct(matrix2X2 x,matrix2X2 y,long long M){
    matrix2X2 z;
    z.a = ((x.a*y.a)%M + (x.b*y.c)%M)%M;
    z.b = ((x.a*y.b)%M + (x.b*y.d)%M)%M;
    z.c = ((x.c*y.a)%M + (x.d*y.c)%M)%M;
    z.d = ((x.c*y.b)%M + (x.d*y.d)%M)%M;
    return z;
}
matrix2X2 matrixInitialize(bool isIdentity){
    matrix2X2 x;
    x.a = x.b = x.c = 1;
    x.d = 0;
    if(isIdentity){
        x.a = x.d = 1; 
        x.b = x.c = 0;
    }
    return x;
}
matrix2X2 matrixPower(long long n,long long M){
    matrix2X2 res = matrixInitialize(true);
    matrix2X2 z = matrixInitialize(false);
    
    while(n>0){
        if(n&1) res = matrixProduct(res,z,M);
        
        z = matrixProduct(z,z,M);
        n/=2;
    }
    return res;
    
}
long long power(long long x,long long y,long long M){
    long long res = 1;
    x%=M;
    while(y>0){
        if(y&1) res = (res*x)%M;
        
        x = (x*x)%M;
        y/=2;
    }
    return res;
}

void getAns(long long p,long long q,long long n){
    p++;q++;n--;
    matrix2X2 z = matrixPower(n,MOD-1); 
    cout <<  (MOD-1+(power(p,z.c,MOD)*power(q,z.a,MOD))%MOD)%MOD << '\n';
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	test{
	    long long p,q,n;
	    cin >> p >> q >> n;
	    if(n==0){
	        cout << p << '\n';
	        continue;
	    }
	    getAns(p,q,n);
	}
}
12

@piyushbhutani Can you please explain why we are taking Modulo by (p-1) instead of p in one part. I didn’t get that part.

13

From quotient remainder theorem:

fib( n ) = k * (p-1) + (fib(n) % (p – 1))

Now using this :

( c^( fib(n) ) ) % p = ( c^((k)*(p-1)) ) % p * ( c ^ (fib(n) % (p – 1))) % p

can anyone explain me how suddenly this equation came right after this (a^(p-1) ) % p = 1 where p is a prime number
i know about fernet little theorem
but this getting me confuse

14

fib(n) = (p-1)k + fib(n)\%(p-1)
c^{fib(n)}\ mod\ p = c^{(p-1)k + fib(n)\%(p-1)}\mod p
c^{fib(n)}\ mod\ p = c^{(p-1)k} c^{fib(n)\%(p-1)}\mod p
c^{fib(n)}\ mod\ p = (c^{p-1})^{k} \times c^{fib(n)\%(p-1)} \mod p
c^{fib(n)}\ mod\ p = (1)^{k} \times c^{fib(n)\%(p-1)}\mod p
c^{fib(n)}\ mod\ p = c^{fib(n)\%(p-1)}\mod p
This doesn’t just apply to fib(n) but all numbers.