이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <stdio.h>
#include <iostream>
#include <array>
#include <cstring>
using namespace std;
struct matrix {
array< array<long long, 2>, 2> v;
matrix() { }
matrix(array< array<long 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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |