Submission #9605

#	Time	Username	Problem	Language	Result	Execution time	Memory
9605		corea	Phibonacci (kriii2_P)	C++14	1 / 4	0 ms	1676 KiB

P

#include <stdio.h>
#include <iostream>
#include <array>
#include <cstring>
using namespace std;

struct matrix {
    array< array<long, 2>, 2> v;
    matrix() { }
    matrix(array< array<long, 2>, 2> &s) {
        v = s;
    }
};

#define REP(i, n) for(int i=0; i < n; ++i)

const long long MOD = 1000000007;

matrix operator * (const matrix &a, const matrix &b) {
    matrix c;
    c.v[0][0] = c.v[0][1] = c.v[1][0] = c.v[1][1] = 0;

    REP(k, 2) REP(i, 2) REP(j, 2) {
        c.v[i][j] += a.v[i][k] * b.v[k][j];
        c.v[i][j] %= MOD;
    }
    return c;
}

matrix I;

matrix power(const matrix &A, long long n) {
    if(n == 0) return I;
    if(n == 1) return A;

    if(n % 2 == 1) {
        return power(A, n - 1) * A;
    }
    else {
        matrix t = power(A, n / 2);
        return t * t;
    }
}

long long fibonacci(long long n) {
    if( n == -1 ) {
        return 1;
    }

    matrix A;
    A.v[0][0] = 0;
    A.v[0][1] = A.v[1][0] = A.v[1][1] =1 ;

    matrix An = power(A, n);
    return An.v[0][1];
}

int main() {
    I.v[0][0] = I.v[1][1] = 1;
    I.v[0][1] = I.v[1][0] = 0;

    long long n, k;
    cin >> n >> k;

    if( k == 1 ) {
        long long x, y;
        x = fibonacci(n);
        y = fibonacci(n - 1);
        cout << x << ' ' << y << endl;
    } else {
        long long rx, ry;
        rx = 0;
        ry = 1;

        long long x, y;
        x = fibonacci(n);
        y = fibonacci(n - 1);
        for( long long i = 1; i <= k; i *= 2 ) {
            if( i & k ) {
                long long a, b, c;
                a = (x * rx) % MOD;
                b = (x * ry) % MOD + (rx * y) % MOD;
                c = (ry * y) % MOD;
                b += a;
                c += a;
                rx = b % MOD;
                ry = c % MOD;
            }
            {
                long long a = (x * x) % MOD + (2 * x * y) % MOD ;
                long long b = (x * x) % MOD + (y * y) % MOD;
                x = a % MOD;
                y = b % MOD;
            }
        }

        {
            long long a = fibonacci(k);
            long long b = rx;

            for( long long i = 1; i <= MOD - 2; i *= 2 ) {
                if( i & (MOD - 2) ) {
                    b *= a;
                    b %= MOD;
                }
                a *= a;
                a %= MOD;
            }

            //cout << a << ' ' << b << endl;
            ry -= fibonacci(k-1) * b;
            ry %= MOD;
            ry += MOD;
            ry %= MOD;
            cout << b << ' ' << ry << endl;
        }

        // cout << rx << ' ' << ry << endl;
    }

    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 3