Fibonacci in TMP, log N time complexity, without using a matrix. | 피보나치, 로그 시복도, 행렬 없이.

fibo_tmp_logn_nomatrix.cpp

#include<iostream>
#include<type_traits>
using namespace std;

using ll=long long;
template<ll val>
using llconst=integral_constant<ll,val>;

constexpr ll mod=1000000007;

template<ll n, int odd>
struct fibo{};
template<ll n>
struct fibo<n,0>:llconst<
((fibo<n/2+1,(n/2+1)&1>::value)
*(fibo<n/2+1,(n/2+1)&1>::value)
%mod
-(fibo<n/2-1,(n/2-1)&1>::value)
*(fibo<n/2-1,(n/2-1)&1>::value)
%mod
+mod)%mod>{};
template<ll n>
struct fibo<n,1>:llconst<
((fibo<n/2+1,(n/2+1)&1>::value)
*(fibo<n/2+1,(n/2+1)&1>::value)
%mod
+(fibo<n/2,(n/2)&1>::value)
*(fibo<n/2,(n/2)&1>::value)
%mod
)%mod>{};
template<>
struct fibo<0,0>:llconst<0>{};
template<>
struct fibo<2,0>:llconst<1>{};
template<>
struct fibo<1,1>:llconst<1>{};

template<ll n>
using fibonacci_t=fibo<n,n&1>;

int main()
{
	ll val=fibonacci_t<1000000000000000000>::value;
	cout<<val;
}