复杂度不对，数组开小了
$f_2 = 1 $，不等于2
by dyyzy_qwq @ 2023-07-12 21:25:54
@[dyyzy](/user/461012) _f₂_ = 1的话就是20pts了，还有数组又开多大呢？ 复杂度 _O(n)_有啥不对勒？
by mediocre_ @ 2023-07-12 21:33:31
$n$ 最大到 $2^{63} - 1$，只能矩阵快速幂啊
by 0x282e202e2029 @ 2023-07-12 21:35:54
```cpp
const long long mod = 1e9 + 7;
struct Matrix
{
long long arr[2][2];
Matrix(long long a = 0, long long b = 0, long long c = 0, long long d = 0)
{
arr[0][0] = a, arr[0][1] = b, arr[1][0] = c, arr[1][1] = d;
}
};
const Matrix I(1, 0, 0, 1), F(1, 1, 1, 0);
Matrix operator * (Matrix a, Matrix b)
{
Matrix res;
for(int i = 0; i < 2; i++)
{
for(int j = 0; j < 2; j++)
{
for(int k = 0; k < 2; k++)
{
res.arr[i][j] += a.arr[i][k] * b.arr[k][j] % mod;
}
}
}
return res;
}
long long fib(long long k)
{
Matrix res = I, n = F;
k--;
while(k)
{
if(k & 1)
{
res = res * n;
}
n = n * n;
k >>= 1;
}
return res.arr[0][0] % mod;
}
```
`fib(n)` 即为答案。
by 0x282e202e2029 @ 2023-07-12 21:37:52
@[Mr_Huang12](/user/565707) 这是因为你数组下标有点混乱，你做题不看数据范围的吗？
by dyyzy_qwq @ 2023-07-12 21:40:22
@[dyyzy](/user/461012) ok
by mediocre_ @ 2023-07-12 21:47:16