题解 P1962 【斐波那契数列】

· · 题解

提供一种没有在题解区看到的打表做法，不使用矩阵乘法，但是比较锻炼观察能力。

虽然本质上是矩阵乘法的展开，但是换了一种理解的方式。

Update On 2022/11/23

修改代码中的小错误，并进一步优化方法和阅读体验。

首先，发现斐波那契数列性质 F_{n + m} = F_{n + 1} \times F_{m} + F_{n} \times F_{m - 1}。（后附证明，这个性质可以由第一种证明方式发现）

将计算看作是从 F_{0} 开始向后移动直到 F_{n}，考虑将移动分解，也就是将 n 拆分为 k 个正整数 T_{i} 的和，从零开始依次向后移动 T_{i} 来不断维护当前答案。

也就是说，我们依次计算 \left\{F_0, F_{T_1}, F_{T_1+T_2}, F_{T_1+T_2+T_3},\cdots\right\}。

向后移动 T_{x} 时，设 c = \sum_{i = 1}^{x - 1} T_{i}，则有我们想要知道的

F_{c + T_{x}} = F_{c + 1} \times F_{T_{x}} + F_{c} \times F_{T_{x} - 1}

由此可知，只有 F_c 是不足够的，我们还需要维护 F_{c + 1}。

F_{c + 1 + T_{x}} = F_{c + (T_x + 1)} = F_{c + 1} \times F_{T_x + 1} + F_{c} \times F_{T_x}

注意，此时将 c 视为原公式中的 n，(T_x + 1) 视为原公式中的 m，这样才能保证仅使用到 F_c 和 F_{c + 1}。否则需要再次转化。

现在我们需要关注的是两个式子中 F_{T_i - 1}, F_{T_i}, F_{T_i + 1} 如何获得。

显然，F_{T_i + 1} = F_{T_i - 1} + F_{T_i}。

因为 T_{i} 没有限制，所以我们可以自行挑选一个集合 S，使得 T 中所有数都来自于 S，并且满足 n 可以分解为 S 中若干个数的和。这样我们只要事先计算出 S 中每个元素 x 的 F_{x - 1}, F_{x}，并在计算时调用即可。

我选择了 2^{i} 的集合。分别令原公式中的 m=n=x，m=n+1=x 则可以得到以下式子：

F_{2x} = F_{x+1} \times F_x + F_x \times F_{x-1} = F_x^2 + 2F_{x-1}\times F_x F_{2x-1} = F_{x}^2 + F_{x-1}^2

据此，我们可以计算得到所有 F_{2^i} 与 F_{2^i-1}。

const ll mod = 1'000'000'007;
vector<ull> FibPow2, FibPow2Minus1;
ull n, f0, f1 = 1, nf0, nf1;
int main ()
{
    std::cin.tie (nullptr), std::ios::sync_with_stdio (false);
    for (ull i = 0; i <= 62; ++i)
    {
        FibPow2.emplace_back (f1), FibPow2Minus1.emplace_back (f0);
        nf0 = f1 * f1 % mod + f0 * f0 % mod;
        nf1 = f1 * f1 % mod + 2 * f0 * f1 % mod;
        if (nf0 >= mod) nf0 -= mod;
        if (nf1 >= mod) nf1 -= mod;
        tie (f0, f1) = mkp (nf0, nf1);
    }
    cin >> n, f0 = 0, f1 = 1;
    while (n)
    {
        static ll i; i = __lg (n & (-n));
        nf0 = FibPow2Minus1[i] * f0 % mod + FibPow2[i] * f1 % mod;
        nf1 = FibPow2[i] * f0 % mod + f1 * (FibPow2[i] + FibPow2Minus1[i]) % mod;
        if (nf0 >= mod) nf0 -= mod;
        if (nf1 >= mod) nf1 -= mod;
        tie (f0, f1) = mkp (nf0, nf1);
        n -= (1ll << i);
    }
    cout << f0 << endl;
    return 0;
}

下附对第一个式子的三种证明方式。

证明方式 1

Consider the following problem: A person climbs up n steps, by taking either one step, or two steps at a time. The total number of ways the person can climb up all the n steps is F_{n+1} (Why?) Now consider climbing m+n−1 steps and split into the cases when the person lands on step n and the cases when the person lands on step n−1 and takes two steps at that point (and so does not land on step n in those cases). These two cases cover all possibilities, and so we have:

F_{m+n}=F_{n+1} \times F_{m}+F_{n} \times F_{m−1}

From StackExchange

考虑一个问题：爬楼梯，一次可以爬一步或者两步，那么爬上 n 级楼梯的方案数量就是 F_{n + 1}。

考虑爬 n + m - 1 级台阶，那么可以把问题分解成两部分：

  1. 经过第 n 级台阶，方案数为 F_{n + 1} \times F_{m}。
  2. 不经过第 n 级台阶，即经过第 n - 1 级台阶并直接到第 n + 1 级台阶，方案数为 F_{n} \times F_{m - 1}。

而总方案数为 F_{n + m}，得证。

证明方式 2

归纳法。

当 n = 1 时，F_{m + 1} = F_{2} \times F_{m} + F_{1} \times F_{m - 1} = F_{m} + F_{m - 1} = F_{m + 1}。

当 n = 2 时，F_{m + 2} = F_{3} \times F_{m} + F_{2} \times F_{m - 1} = 2 \times F_{m} + F_{m - 1} = F_{m + 2}。

若已知条件如下：

\left\{\begin{array}{ccc} F_{m + n - 1} = F_{n} \times F_{m} + F_{n - 1} + F_{m - 1} \\\ F_{m + n - 2} = F_{n - 1} \times F_{m} + F_{n - 2} + F_{m - 1}\end{array}\right.

则将两式相加，得到：F_{n + m} = F_{n + 1} \times F_{m} + F_{n} \times F_{m - 1}。

由于已证明 n = 1, 2 时命题成立，故可以将结论推广到正整数集。

证明方式 3

我们知道，对于 M=\left[\begin{array}{ccc} 1 & 1 \\\ 1 & 0\end{array}\right]，有 M^{n} = \left[\begin{array}{cc} F_{n+1} &\!\! F_n \\\ F_n &\!\! F_{n-1} \end{array}\right]。

M_{n+m} = M_n*M_m = \left[\begin{array}{ccc} F_{n+1} & F_n \\\ F_n & F_{n-1} \end{array}\right]\times\left[\begin{array}{ccc} F_{m+1} & F_m \\\ F_m & F_{m-1} \end{array}\right] = \left[\begin{array}{ccc} F_{n+1}F_{m+1} + F_nF_m & F_{n+1}F_m + F_nF_{m-1} \\\ F_nF_{m+1} + F_{n-1}F_m & F_{n}F_{m} + F_{n-1}F_{m-1} \end{array}\right]

得证。