(F_n = egin{cases} 1 & (n leq 2)\ F_{n-1} + F_{n-2} & (n geq 3 )end{cases})
请你求出 (F_n ext{ mod } 10^9+7) 的值。
(egin{cases} F_{n+1} = 1 × F_{n} + 1 × F_{n-1} \ F_n = 1× F_n + 0× F_{n - 1} end{cases})
( Rightarrow left[egin{array}{ccc} F_{n+1}\ F_n end{array} ight] = left[egin{array}{ccc} 1 & 1\ 1 & 0 end{array} ight] × left[egin{array}{ccc} F_n\ F_{n- 1} end{array} ight] )
( Rightarrow left[egin{array}{ccc} F_{n+1}\ F_n end{array} ight] = left[egin{array}{ccc} 1 & 1\ 1 & 0 end{array} ight] ^ {n - 1} × left[egin{array}{ccc} F_2\ F_1 end{array} ight] )
( Rightarrow left[egin{array}{ccc} F_{n+1}\ color{red}{F_n} end{array} ight] = left[egin{array}{ccc} 1 & 1\ 1 & 0 end{array} ight] ^ {n - 1} × left[egin{array}{ccc} 1\ 1 end{array} ight] )
则初始化矩阵为 (left[egin{array}{ccc}1\1end{array} ight]),快速幂 (n-1) 次转移矩阵 (left[egin{array}{ccc} 1 & 1\ 1 & 0 end{array} ight]),得到的 (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
", Ans.m[2][1] % mod);
return 0;
}