oj.uz

Submission #9683

# Submission time Handle Problem Language Result Execution time Memory
9683 2014-09-28T08:05:26 Z maniac Phibonacci (kriii2_P) C++
1 / 4
 0 ms 1088 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1088 KB Output is correct
2 Correct 0 ms 1088 KB Output is correct
3 Correct 0 ms 1088 KB Output is correct
4 Correct 0 ms 1088 KB Output is correct
5 Correct 0 ms 1088 KB Output is correct
6 Correct 0 ms 1088 KB Output is correct
7 Correct 0 ms 1088 KB Output is correct
8 Correct 0 ms 1088 KB Output is correct
9 Correct 0 ms 1088 KB Output is correct
10 Correct 0 ms 1088 KB Output is correct
11 Correct 0 ms 1088 KB Output is correct
12 Correct 0 ms 1088 KB Output is correct
13 Correct 0 ms 1088 KB Output is correct
14 Correct 0 ms 1088 KB Output is correct
15 Correct 0 ms 1088 KB Output is correct
16 Correct 0 ms 1088 KB Output is correct
17 Correct 0 ms 1088 KB Output is correct
18 Correct 0 ms 1088 KB Output is correct
19 Correct 0 ms 1088 KB Output is correct
20 Correct 0 ms 1088 KB Output is correct

Subtask #2
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1088 KB Output isn't correct
2 Halted 0 ms 0 KB -