The power of Fibonacci - 题解

标签与难度

标签: 数论, 中国剩余定理, 斐波那契, 快速幂, 周期性, 循环节难度: 2300

题目大意喵~

各位Master，下午好喵~ Amy小姐姐又给B先生出难题啦，我们快来帮帮他吧！

题目是这样哒：我们都知道斐波那契数列 $F_i$ ，它的定义是 $F_0 = 0, F_1 = 1$ ，以及 $F_i = F_{i-1} + F_{i-2}$ 。现在给定两个整数 $n$ 和 $m$ ，我们需要计算下面这个式子的值：

\sum_{i=0}^{n} F_i^m

因为结果可能会非常非常大，所以我们需要把答案对 $1000000000$ 取模。其中 $n$ 可能会是一个天文数字哦，所以直接暴力循环肯定是不行的说！

解题思路分析

喵呜~ 看到这么大的 $n$ 和一个奇怪的模数，本能地感觉这里面一定有数学的魔法，对吧？

首先，我们来仔细看看这个模数 $1000000000$ 。它等于 $10^9$ ，并不是一个质数呢。这在数论问题里是一个重要的信号！我们可以把它分解质因数：

10^9 = (2 \cdot 5)^9 = 2^9 \cdot 5^9 = 512 \cdot 1953125

$512$ 和 $1953125$ 是互质的！看到互质的因数，我们的小脑袋里是不是就亮起了一盏名为“中国剩余定理 (Chinese Remainder Theorem, CRT)”的灯泡呢？喵~

没错！我们可以把原问题拆解成两个子问题：

计算 $\left(\sum_{i=0}^{n} F_i^m\right) \pmod{512}$ ，得到余数 $ans_1$ 。
计算 $\left(\sum_{i=0}^{n} F_i^m\right) \pmod{1953125}$ ，得到余数 $ans_2$ 。

然后，我们就可以通过解下面的同余方程组，来找到唯一在 $\pmod{10^9}$ 意义下的解啦：

\begin{cases} x \equiv ans_1 \pmod{512} \\ x \equiv ans_2 \pmod{1953125} \end{cases}

这就像是分别从两个不同的角度看一只猫猫，最后把信息拼起来得到猫猫的全貌一样，喵~

那么，怎么解决子问题呢？比如说，如何计算 $\left(\sum_{i=0}^{n} F_i^m\right) \pmod P$ 呢？（这里的 $P$ 就是 $512$ 或者 $1953125$ ）

这里就要用到斐波那契数列一个超级可爱的性质啦：周期性！斐波那契数列在任何模数 $k$ 下都是有周期的，这个周期被称为 皮萨诺周期 (Pisano Period)，记作 $\pi(k)$ 。也就是说， $F_{i} \pmod k$ 这个序列会无限循环。

如果 $F_i \pmod P$ 是周期性的，那么 $F_i^m \pmod P$ 这个序列当然也是周期性的啦！它的周期一定是 $\pi(P)$ 的一个约数。为了方便，我们直接用 $\pi(P)$ 作为周期来计算，这是完全没问题的说。

一个已知的结论是，对于素数 $p$ 的幂 $p^k$ ，斐波那契数列的周期是 $\pi(p^k) = p^{k-1} \cdot \pi(p)$ 。

对于 $P_1 = 512 = 2^9$ ：我们知道 $\pi(2) = 3$ 。所以周期是 $\pi(2^9) = 2^{9-1} \cdot \pi(2) = 2^8 \cdot 3 = 256 \cdot 3 = 768$ 。
对于 $P_2 = 1953125 = 5^9$ ：我们知道 $\pi(5) = 20$ 。所以周期是 $\pi(5^9) = 5^{9-1} \cdot \pi(5) = 5^8 \cdot 20 = 7812500$ 。

好啦，现在我们知道了周期，怎么利用它来求和呢？假设我们要计算 $\sum_{i=0}^{n} A_i \pmod P$ ，其中 $A_i = F_i^m \pmod P$ ，并且 $A_i$ 的周期是 Period。我们可以把 $n$ 分成完整的周期部分和零头部分： $n = q \cdot \text{Period} + r$ ，这里 $q = \lfloor n / \text{Period} \rfloor$ 是完整周期的数量， $r = n \pmod{\text{Period}}$ 是零头。

那么总和就可以写成：

\sum_{i=0}^{n} A_i = q \cdot \left(\sum_{i=0}^{\text{Period}-1} A_i\right) + \sum_{i=0}^{r} A_i

为了计算这个，我们可以预处理出周期内的前缀和数组 prefix_sum，其中 prefix_sum[k] $= \sum_{i=0}^{k} A_i \pmod P$ 。于是， $\sum_{i=0}^{\text{Period}-1} A_i$ 就是 prefix_sum[Period-1]，而 $\sum_{i=0}^{r} A_i$ 就是 prefix_sum[r]。所以，最终的答案就是：

ans = \left( \lfloor n / \text{Period} \rfloor \cdot \text{prefix\_sum}[\text{Period}-1] + \text{prefix\_sum}[n \pmod{\text{Period}}] \right) \pmod P

这个方法是不是很清晰呢，呐？

总结一下我们的完整计划：

分解问题: 将模 $10^9$ 的问题分解为模 $512$ 和模 $1953125$ 的两个子问题。
计算周期: 确定斐波那契数列在模 $512$ 和 $1953125$ 下的周期，分别是 $768$ 和 $7812500$ 。
预处理: 对每个子问题，我们都在一个周期内计算出 $F_i^m$ 的前缀和。
计算子问题答案: 利用上面推导出的公式，快速计算出 $ans_1$ 和 $ans_2$ 。
合并答案: 使用中国剩余定理，将 $ans_1$ 和 $ans_2$ 合并，得到最终答案！

Let's get our paws dirty and start coding! 喵~

代码实现

cpp

#include <iostream>
#include <vector>

// 使用 long long 来防止计算过程中溢出，喵~
using int64 = long long;

// 快速幂模板，用于计算 (base^exp) % mod
// a^b mod m
int64 power(int64 base, int64 exp, int64 mod) {
    int64 res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (__int128)res * base % mod;
        base = (__int128)base * base % mod;
        exp /= 2;
    }
    return res;
}

// 扩展欧几里得算法，用来求解 ax + by = gcd(a, b)
// 我们用它来求模逆元，这是CRT的关键一步！
int64 extended_gcd(int64 a, int64 b, int64 &x, int64 &y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    int64 x1, y1;
    int64 gcd = extended_gcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return gcd;
}

// 模逆元函数
// 求 a 在模 m 下的逆元
int64 mod_inverse(int64 a, int64 m) {
    int64 x, y;
    int64 g = extended_gcd(a, m, x, y);
    if (g != 1) return -1; // 不存在逆元
    return (x % m + m) % m;
}

// 核心计算函数：计算在某个模数下的总和
// n, m 是题目输入, modulus 是模数, period 是斐波那契数列在该模数下的周期
int64 solve_for_mod(int64 n, int64 m, int64 modulus, int period) {
    // 预处理斐波那契数和我们要求的前缀和
    std::vector<int64> fib(period);
    std::vector<int64> prefix_sum(period);

    // 计算周期内的斐波那契数
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i < period; ++i) {
        fib[i] = (fib[i - 1] + fib[i - 2]) % modulus;
    }

    // 计算 F_i^m 的前缀和
    // F_0^m = 0^m = 0 (当 m>0)
    prefix_sum[0] = 0;
    for (int i = 1; i < period; ++i) {
        int64 term = power(fib[i], m, modulus);
        prefix_sum[i] = (prefix_sum[i - 1] + term) % modulus;
    }

    // 利用周期性计算总和
    int64 num_periods = n / period;
    int64 remainder_len = n % period;

    int64 sum_one_period = prefix_sum[period - 1];
    
    // 注意这里要用 __int128 防止 num_periods * sum_one_period 溢出
    int64 total_sum = ((__int128)num_periods * sum_one_period) % modulus;
    total_sum = (total_sum + prefix_sum[remainder_len]) % modulus;
    
    return total_sum;
}

int main() {
    // 为了更快的输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int64 n, m;
    std::cin >> n >> m;

    // 我们的两个子问题
    int64 mod1 = 512;
    int period1 = 768; // Pisano period for 2^9
    int64 mod2 = 1953125;
    int period2 = 7812500; // Pisano period for 5^9

    int64 ans1 = solve_for_mod(n, m, mod1, period1);
    int64 ans2 = solve_for_mod(n, m, mod2, period2);

    // 中国剩余定理 (CRT) 合并答案
    // 我们有 x = ans1 (mod mod1) 和 x = ans2 (mod mod2)
    // 根据CRT，解为 x = ans1*M2*inv(M2,mod1) + ans2*M1*inv(M1,mod2)
    // 其中 M1=mod2, M2=mod1
    // 简化后，一个常见的形式是 x = ans1 + mod1 * k
    // 代入第二个方程： ans1 + mod1 * k ≡ ans2 (mod mod2)
    // k * mod1 ≡ ans2 - ans1 (mod mod2)
    // k ≡ (ans2 - ans1) * inv(mod1, mod2) (mod mod2)
    
    int64 inv_mod1_mod2 = mod_inverse(mod1, mod2);
    int64 k = ((__int128)(ans2 - ans1 + mod2) % mod2 * inv_mod1_mod2) % mod2;
    
    int64 final_ans = ans1 + (__int128)k * mod1;
    
    int64 final_mod = 1000000000;
    std::cout << (final_ans % final_mod + final_mod) % final_mod << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(P_1 \log m + P_2 \log m)$ 我们的主要计算开销在于两个 solve_for_mod 函数。在每个函数中，我们都需要预处理一个周期内的斐波那契数（ $O(\text{Period})$ ）和前缀和。计算前缀和时，对每个数都要做一次快速幂，所以这部分是 $O(\text{Period} \cdot \log m)$ 。因此，总的时间复杂度由两个周期的长度决定，即 $O(P_1 \log m + P_2 \log m)$ ，其中 $P_1 = 768$ ， $P_2 = 7812500$ 。这是一个固定的、与输入 $n$ 无关的预处理时间，所以非常快！
空间复杂度: $O(P_1 + P_2)$ 我们需要存储两个周期的斐波那契数和前缀和数组。所以空间复杂度就是 $O(P_1 + P_2)$ 。虽然 $P_2$ 比较大，但在现代计算机的内存限制下是完全可以接受的，喵~

知识点总结

这道题真是一次奇妙的数论探险呢！我们来总结一下这次旅程中学到的魔法吧：

中国剩余定理 (CRT): 当遇到一个合数模数时，可以尝试将其分解为互质的几个数的乘积，然后对每个数单独求解，最后用CRT合并答案。这是处理这类问题的标准武器之一！
斐波那契数列的周期性 (皮萨诺周期): 斐波那契数列在任何模数下都是周期性的。这个美妙的性质是解决涉及斐波那契和巨大下标 $n$ 的问题的关键。
周期序列求和: 对于一个周期为 $P$ 的序列，其前 $n$ 项和可以通过 (n/P) * (一个周期的和) + (n%P 项的和) 快速计算。预处理前缀和数组是实现这一点的绝佳方式。
扩展欧几里得算法: 它是实现CRT和求解模逆元的基础工具，是数论工具箱里必不可少的一把瑞士军刀，呐。
__int128: 在处理 long long 相乘可能爆 long long 的情况时，使用 __int128 是一个非常方便的技巧，可以避免复杂的、手写的龟速乘。

希望这篇题解能帮助你更好地理解这些有趣的数学知识！下次遇到难题也别怕，我们一起动动小脑筋，一定能解决的！喵~

The power of Fibonacci - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​