一、题目
二、分析
比较基础的递推式转换为矩阵递推，这里因为$n$会超出$int$类型，所以需要用矩阵快速幂加快递推。
三、AC代码
1 #include <bits/stdc++.h>
2
3 using namespace std;
4 #define ll long long
5 #define Min(a,b) ((a)>(b)?(b):(a))
6 #define Max(a,b) ((a)>(b)?(a):(b))
7 const ll mod = 1000000007;
8
9 struct Matrix
10 {
11 ll a[3][3];
12 Matrix() { memset(a, 0, sizeof(a)); }
13 Matrix operator*(const Matrix & b) const
14 {
15 Matrix res;
16 for(int i = 0; i < 2; i ++)
17 {
18 for(int j = 0; j < 2; j++)
19 {
20 for(int k = 0; k < 2; k++)
21 {
22 res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % mod;
23 }
24 }
25 }
26 return res;
27 }
28 } ans, base;
29
30 void Pow(ll b)
31 {
32 while(b)
33 {
34 if(b&1)
35 {
36 ans = ans * base;
37 }
38 base = base * base;
39 b >>= 1;
40 }
41 }
42
43 void init()
44 {
45 base.a[0][0] = 0, base.a[0][1] = 1;
46 base.a[1][0] = 1, base.a[1][1] = 1;
47 ans.a[0][0] = 1, ans.a[0][1] = 1;
48 }
49
50 int main()
51 {
52
53 ll n;
54 while(std::cin>>n)
55 {
56 if(n > 2)
57 {
58 init();
59 Pow(n - 2);
60 std::cout << ans.a[0][1] << std::endl;
61 }
62 else
63 {
64 std::cout << "1" << std::endl;
65 }
66 }
67 return 0;
68 }