\(F_n = \begin{cases} 1 & (n \leq 2)\\ F_{n-1} + F_{n-2} & (n \geq 3 )\end{cases}\)
请你求出 \(F_n \text{ mod } 10^9+7\) 的值。
\(\begin{cases} F_{n+1} = 1 × F_{n} + 1 × F_{n-1} \\ F_n = 1× F_n + 0× F_{n - 1} \end{cases}\)
\( \Rightarrow \left[\begin{array}{ccc} F_{n+1}\\ F_n \end{array}\right] = \left[\begin{array}{ccc} 1 & 1\\ 1 & 0 \end{array}\right] × \left[\begin{array}{ccc} F_n\\ F_{n- 1} \end{array}\right] \)
\( \Rightarrow \left[\begin{array}{ccc} F_{n+1}\\ F_n \end{array}\right] = \left[\begin{array}{ccc} 1 & 1\\ 1 & 0 \end{array}\right] ^ {n - 1} × \left[\begin{array}{ccc} F_2\\ F_1 \end{array}\right] \)
\( \Rightarrow \left[\begin{array}{ccc} F_{n+1}\\ \color{red}{F_n} \end{array}\right] = \left[\begin{array}{ccc} 1 & 1\\ 1 & 0 \end{array}\right] ^ {n - 1} × \left[\begin{array}{ccc} 1\\ 1 \end{array}\right] \)
则初始化矩阵为 \(\left[\begin{array}{ccc}1\\1\end{array}\right]\)，快速幂 \(n-1\) 次转移矩阵 \(\left[\begin{array}{ccc} 1 & 1\\ 1 & 0 \end{array}\right]\)，得到的 \(Ans_{2, 1}\) 即为答案。
创建
struct STU{
ll m[3][3];
STU(){memset(m, 0, sizeof m);}
STU operator*(const STU &b) const{
STU x;
for(int i = 1; i <= 2; ++i)
for(int j = 1; j <= 2; ++j)
for(int k = 1; k <= 2; ++k)
x.m[i][j] = (x.m[i][j] + m[i][k] * b.m[k][j]) % mod;
return x;
}
} Ans, Base;
初始化
void Pre()
{
Ans.m[1][1] = Ans.m[2][1] = 1;
Base.m[1][1] = Base.m[1][2] = Base.m[2][1] = 1;
}
计算
void ksm(ll b)
{
while(b)
{
if(b & 1)
Ans = Ans * Base;
Base = Base * Base;
b >>= 1;
}
}
int main()
{
ll n = read();
Pre();
ksm(n - 1);
printf("%lld\n", Ans.m[2][1] % mod);
return 0;
}