题解：P9777 [HUSTFC 2023] Fujisaki 讨厌数学

Sk_sync_opener · 2025-02-13 19:13:18 · 题解

首先学过初中数学的都知道 \left( x ^ {i} + x ^ {-i} \right) \times \left(x + x ^ {-1}\right) = \left(x ^ {i + 1} + x ^ {-i-1}\right) + \left(x ^ {i - 1} + x ^ {-i + 1}\right)。

令 f(i) = x ^ {i} + x ^ {i - 1}，则上式转化为 f(i) \times k = f(i + 1) + f(i - 1)。

移项，得 f(i) \times k - f(i - 1) = f(i + 1)。那么就可以愉快地矩阵快速幂了！

注意特判 0 \leq n \leq 2 的情况。然后注意输出答案需要使用 write((ans + mod) % mod); 防止出现负数。