Submission #9683

#	Time	Username	Problem	Language	Result	Execution time	Memory
9683		maniac	Phibonacci (kriii2_P)	C++98	1 / 4	0 ms	1088 KiB

P

#include <cstdio>

const long long MOD(1000000007);

typedef struct matrix{
    long long d[2][2];
}Matrix;
 
Matrix F={1, 1, 1, 0};
 
Matrix m_Mul(Matrix A, Matrix B){
    Matrix C;
    C.d[0][0]=(A.d[0][0]*B.d[0][0]+A.d[0][1]*B.d[1][0])%MOD;
    C.d[0][1]=(A.d[0][0]*B.d[1][0]+A.d[0][1]*B.d[1][1])%MOD;
    C.d[1][0]=(A.d[1][0]*B.d[0][0]+A.d[1][1]*B.d[1][0])%MOD;
    C.d[1][1]=(A.d[1][0]*B.d[1][0]+A.d[1][1]*B.d[1][1])%MOD;
    return C;
}
 
Matrix m_Power(Matrix A, long long n){
    if(n>1){
        A=m_Power(A, n/2);
        A=m_Mul(A, A);
        if(n&1)
            A=m_Mul(A, F);
    }
    return A;
}
 
int main(){
    long long n, m;
    scanf("%lld %lld", &n, &m);
	if (n == 0) {
		// phi^0 = 1 = F(0) * phi + F(-1) = 0 * phi + 1
		puts("0 1");
		return 0;
	} else if (n == 1) {
		puts("1 0");
		return 0;
	}
    Matrix A={1, 1, 1, 0}, B={1, 1, 1, 0};
    A=m_Power(A, n-1);
    B=m_Power(B, n);
    printf("%lld %lld\n", B.d[0][1], A.d[0][1]);
    return 0;
}

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