그냥 n번째 피보나치 수를 구하는 문제인데 값이 커서 최적화를 잘 시켜야 한다.
그냥 이 행렬 곱을 이용해서 구하면 된다.
행렬의 n제곱을 계산하면 되는데 분할정복 느낌?으로 n/2제곱을 계산하는 식으로 재귀함수를 거치면
log(n)의 시간만에 구할 수 있어서 빠르다.
#include<stdio.h>
long long N;
long long K = 1000000007;
long long dp[2][2];
void fibo(long long n){
if(n==1) return;
long long m = n/2;
fibo(m);
long long mm[2][2];
mm[0][0] = dp[0][0]*dp[0][0]%K + dp[0][1]*dp[1][0]%K;
mm[0][1] = dp[0][0]*dp[0][1]%K + dp[0][1]*dp[1][1]%K;
mm[1][0] = dp[1][0]*dp[0][0]%K + dp[1][1]*dp[1][0]%K;
mm[1][1] = dp[1][0]*dp[0][1]%K + dp[1][1]*dp[1][1]%K;
mm[0][0] %= K;
mm[0][1] %= K;
mm[1][0] %= K;
mm[1][1] %= K;
if(n%2==1){
dp[0][0] = (mm[0][0] + mm[0][1]) % K;
dp[0][1] = mm[0][0] % K;
dp[1][0] = (mm[1][0] + mm[1][1]) % K;
dp[1][1] = mm[1][0] % K;
}
else{
dp[0][0] = mm[0][0];
dp[0][1] = mm[0][1];
dp[1][0] = mm[1][0];
dp[1][1] = mm[1][1];
}
return;
}
int main()
{
dp[0][0] = 1;
dp[0][1] = 1;
dp[1][0] = 1;
dp[1][1] = 0;
scanf("%lld",&N);
fibo(N);
printf("%lld",dp[0][1]);
}구현은 그냥 2차원 배열로 행렬 곱을 하나하나 계산해서 했다.
