제출 #9801

#제출 시각아이디문제언어결과실행 시간메모리
9801veckalPhibonacci (kriii2_P)C++14
0 / 4
0 ms1088 KiB
#include<stdio.h> typedef long long ll; const int MOD = 1000000000 + 7; ll n, k; struct Matrix { ll mat[2][2]; Matrix() { mat[0][0]=mat[0][1]=mat[1][0]=1; mat[1][1]=0; } }; Matrix operator *(Matrix& A, Matrix& B) { Matrix ret; ret.mat[0][0] = ret.mat[0][1] = ret.mat[1][0] = ret.mat[1][1] = 0; for (int i=0; i<2; ++i) for (int j=0; j<2; ++j) for (int k=0; k<2; ++k) ret.mat[i][j] = (ret.mat[i][j] + A.mat[i][k] * A.mat[k][j])%MOD; return ret; } Matrix identity() { Matrix ret; ret.mat[0][0] = ret.mat[1][1] = 1; ret.mat[0][1] = ret.mat[1][0] = 0; return ret; } Matrix pow(ll exp) { Matrix ret; if (exp == 1) return ret; ret = pow(exp>>1); ret = ret * ret; Matrix base; if (exp&1) ret = ret * base; return ret; } int main() { scanf("%lld%lld", &n, &k); if (k == 1) { Matrix fib = pow(n); printf("%lld %lld\n", fib.mat[0][1], fib.mat[1][1]); } else if (n == 1) { puts("1 0"); } else if (n == 0) { puts("0 1"); } else if (k == 2) { Matrix fib = pow(n-1); ll ans2 = fib.mat[1][1]; Matrix base; fib = fib * base; ll ans1 = fib.mat[0][1]; printf("%lld %lld\n", ans1, ans2); } else puts("-1"); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...