题目
相信小伙伴们都学过斐波那契数列，它是这样的一个数列： <math> <semantics> <mrow> <mn> 1 </mn> <mo separator="true"> , </mo> <mn> 1 </mn> <mo separator="true"> , </mo> <mn> 2 </mn> <mo separator="true"> , </mo> <mn> 3 </mn> <mo separator="true"> , </mo> <mn> 5 </mn> <mo separator="true"> , </mo> <mn> 8 </mn> <mo separator="true"> , </mo> <mn> 13 </mn> <mo separator="true"> , </mo> <mn> 21 </mn> <mo> ⋯ </mo> </mrow> <annotation encoding="application/x-tex"> 1,1,2,3,5,8,13,21\cdots </annotation> </semantics> </math>1,1,2,3,5,8,13,21⋯。
用 <math> <semantics> <mrow> <msub> <mi> f </mi> <mi> n </mi> </msub> </mrow> <annotation encoding="application/x-tex"> f_n </annotation> </semantics> </math>fn 表示斐波那契数列的第 <math> <semantics> <mrow> <mi> n </mi> </mrow> <annotation encoding="application/x-tex"> n </annotation> </semantics> </math>n 项，则有： <math> <semantics> <mrow> <msub> <mi> f </mi> <mn> 1 </mn> </msub> <mo> = </mo> <msub> <mi> f </mi> <mn> 2 </mn> </msub> <mo> = </mo> <mn> 1 </mn> </mrow> <annotation encoding="application/x-tex"> f_1 = f_2 = 1 </annotation> </semantics> </math>f1=f2=1， <math> <semantics> <mrow> <msub> <mi> f </mi> <mi> n </mi> </msub> <mo> = </mo> <msub> <mi> f </mi> <mrow> <mi> n </mi> <mo> − </mo> <mn> 1 </mn> </mrow> </msub> <mo> + </mo> <msub> <mi> f </mi> <mrow> <mi> n </mi> <mo> − </mo> <mn> 2 </mn> </mrow> </msub> <mo> ( </mo> <mi> n </mi> <mo> > </mo> <mn> 2 </mn> <mo> ) </mo> </mrow> <annotation encoding="application/x-tex"> f_n = f_{n-1} + f_{n-2} (n > 2) </annotation> </semantics> </math>fn=fn−1+fn−2(n>2)。
输入一个 <math> <semantics> <mrow> <mi> n </mi> </mrow> <annotation encoding="application/x-tex"> n </annotation> </semantics> </math>n，求出 <math> <semantics> <mrow> <msub> <mi> f </mi> <mi> n </mi> </msub> </mrow> <annotation encoding="application/x-tex"> f_n </annotation> </semantics> </math>fn 对 <math> <semantics> <mrow> <mn> 1000000007 </mn> <mo> ( </mo> <mn> 1 </mn> <msup> <mn> 0 </mn> <mn> 9 </mn> </msup> <mo> + </mo> <mn> 7 </mn> <mo> ) </mo> </mrow> <annotation encoding="application/x-tex"> 1000000007(10^9+7) </annotation> </semantics> </math>1000000007(109+7) 取模结果。
输入格式
输入一个整数 <math> <semantics> <mrow> <mi> n </mi> <mo> ( </mo> <mn> 1 </mn> <mo> ≤ </mo> <mi> n </mi> <mo> ≤ </mo> <mn> 100000 </mn> <mo> ) </mo> </mrow> <annotation encoding="application/x-tex"> n(1 \le n \le 100000) </annotation> </semantics> </math>n(1≤n≤100000)。
输出格式
输入 <math> <semantics> <mrow> <msub> <mi> f </mi> <mi> n </mi> </msub> <mrow> <mi mathvariant="normal"> m </mi> <mi mathvariant="normal"> o </mi> <mi mathvariant="normal"> d </mi> </mrow> <mn> 1000000007 </mn> </mrow> <annotation encoding="application/x-tex"> f_n \mathrm{mod} 1000000007 </annotation> </semantics> </math>fnmod1000000007 的值。
样例输入
3
样例输出
2
题解
斐波那契数列的规则是
- <math> <semantics> <mrow> <msub> <mi> f </mi> <mn> 1 </mn> </msub> <mo> = </mo> <msub> <mi> f </mi> <mn> 2 </mn> </msub> <mo> = </mo> <mn> 1 </mn> </mrow> <annotation encoding="application/x-tex"> f_1 = f_2 = 1 </annotation> </semantics> </math>f1=f2=1
- <math> <semantics> <mrow> <msub> <mi> f </mi> <mi> n </mi> </msub> <mo> = </mo> <msub> <mi> f </mi> <mrow> <mi> n </mi> <mo> − </mo> <mn> 1 </mn> </mrow> </msub> <mo> + </mo> <msub> <mi> f </mi> <mrow> <mi> n </mi> <mo> − </mo> <mn> 2 </mn> </mrow> </msub> <mo> ( </mo> <mi> n </mi> <mo> > </mo> <mn> 2 </mn> <mo> ) </mo> </mrow> <annotation encoding="application/x-tex"> f_n = f_{n-1} + f_{n-2} (n > 2) </annotation> </semantics> </math>fn=fn−1+fn−2(n>2)
我们用 <math> <semantics> <mrow> <msub> <mi> f </mi> <mn> 1 </mn> </msub> </mrow> <annotation encoding="application/x-tex"> f_1 </annotation> </semantics> </math>f1 存储两项和，前面的一项，用 <math> <semantics> <mrow> <msub> <mi> f </mi> <mn> 2 </mn> </msub> </mrow> <annotation encoding="application/x-tex"> f_2 </annotation> </semantics> </math>f2 存储两项和，后面的一项，所求和用 <math> <semantics> <mrow> <msub> <mi> f </mi> <mn> 1 </mn> </msub> </mrow> <annotation encoding="application/x-tex"> f_1 </annotation> </semantics> </math>f1 存储，由于当前 <math> <semantics> <mrow> <msub> <mi> f </mi> <mn> 1 </mn> </msub> </mrow> <annotation encoding="application/x-tex"> f_1 </annotation> </semantics> </math>f1 相对 <math> <semantics> <mrow> <msub> <mi> f </mi> <mn> 2 </mn> </msub> </mrow> <annotation encoding="application/x-tex"> f_2 </annotation> </semantics> </math>f2 是"后面"的一项了，所以将 <math> <semantics> <mrow> <msub> <mi> f </mi> <mn> 1 </mn> </msub> </mrow> <annotation encoding="application/x-tex"> f_1 </annotation> </semantics> </math>f1 和 <math> <semantics> <mrow> <msub> <mi> f </mi> <mn> 2 </mn> </msub> </mrow> <annotation encoding="application/x-tex"> f_2 </annotation> </semantics> </math>f2 值互换
#include<iostream>
#include<algorithm>
using namespace std;
const int Mod = 1000000007;
int main(){
int n;
cin>>n;
int f1 = 1;
int f2 = 1;
for(int i=3;i<=n;i++){
f1 = (f1+f2)%Mod;
swap(f1,f2);
}
cout<<f2%Mod;
return 0;
}
京公网安备 11010502036488号