Problem 906: Fibonacci Modular Properties

Mathematical Analysis

The Fibonacci Recurrence and Its Matrix Form

The Fibonacci sequence satisfies $F_n = F_{n-1} + F_{n-2}$ with $F_1 = F_2 = 1$. This recurrence can be expressed as a matrix equation:

By induction:

Proof of (2). Base case $n=1$: the matrix is $\begin{pmatrix} F_2 & F_1 \\ F_1 & F_0 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$. Inductive step: if $Q^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}$, then $Q^{n+1} = Q^n \cdot Q = \begin{pmatrix} F_{n+1}+F_n & F_{n+1} \\ F_n+F_{n-1} & F_n \end{pmatrix} = \begin{pmatrix} F_{n+2} & F_{n+1} \\ F_{n+1} & F_n \end{pmatrix}$. $\square$

Telescoping Sum Identity

Theorem. $\sum_{k=1}^{n} F_k = F_{n+2} - 1$.

Proof. Write $F_k = F_{k+2} - F_{k+1}$ (rearranging the recurrence). Then:

Binet’s Formula and Growth Rate

The closed-form expression is:

Since $|\psi| < 1$, $F_n \sim \phi^n / \sqrt{5}$ for large $n$. For $n = 10^7$: $\log_{10} F_{10^7} \approx 10^7 \cdot \log_{10} \phi \approx 2{,}089{,}876$ digits.

Pisano Period

The Fibonacci sequence modulo $m$ is periodic with period $\pi(m)$ called the Pisano period. For a prime $p$:

• If $p = 5$: $\pi(5) = 20$
• If $p \equiv \pm 1 \pmod{5}$: $\pi(p) \mid p - 1$
• If $p \equiv \pm 2 \pmod{5}$: $\pi(p) \mid 2(p + 1)$

For $p = 10^9 + 7$: since $10^9 + 7 \equiv 2 \pmod{5}$, we have $\pi(p) \mid 2(10^9 + 8)$. The exact period is very large, so we use matrix exponentiation rather than period detection.

Fast Doubling Identities

An alternative to matrix exponentiation uses the fast doubling formulas derived from (2):

These allow computing $F_n \bmod p$ in $O(\log n)$ time without matrix multiplication overhead.

Concrete Values

Editorial

To compute $Q^n$ in $O(\log n)$ multiplications. We compute $F_{N+2} \bmod p$ where $N = 10^7$ using matrix exponentiation or fast doubling. We then write $n$ in binary: $n = b_k b_{k-1} \cdots b_0$. Finally, iterate over each bit from MSB to LSB: $R \leftarrow R^2$; if $b_i = 1$: $R \leftarrow R \cdot Q$.

Pseudocode

Compute $F_{N+2} \bmod p$ where $N = 10^7$ using matrix exponentiation or fast doubling
Return $(F_{N+2} - 1) \bmod p$
Write $n$ in binary: $n = b_k b_{k-1} \cdots b_0$
Initialize $R = I$ (identity)
For each bit from MSB to LSB: $R \leftarrow R^2$; if $b_i = 1$: $R \leftarrow R \cdot Q$
Each $2 \times 2$ matrix multiplication uses 8 multiplications and 4 additions modulo $p$

Proof of Correctness

Theorem. The computation $S = (F_{N+2} \bmod p) - 1 \bmod p$ correctly gives $\sum_{k=1}^{N} F_k \bmod p$.

Proof. The telescoping identity shows $S = F_{N+2} - 1$ over $\mathbb{Z}$. Matrix exponentiation computes $F_{N+2} \bmod p$ exactly (all intermediate operations are modular, and the Fibonacci recurrence is a linear recurrence preserved by modular reduction). Subtraction modulo $p$ is standard. $\square$

Complexity Analysis

• Matrix exponentiation: $O(\log N)$ matrix multiplications, each $O(1)$ for $2 \times 2$ matrices. Total: $O(\log N)$ time, $O(1)$ space.
• Fast doubling: Same $O(\log N)$ complexity with smaller constant (avoids matrix overhead).
• Iterative computation: $O(N)$ time, $O(1)$ space. Feasible for $N = 10^7$ but slower.
• Closed-form (Binet): Not directly usable modulo $p$ without computing $\sqrt{5} \bmod p$ (possible since 5 is a QR mod some primes).

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 906: Fibonacci Modular Properties
 *
 * Compute sum_{k=1}^{10^7} F_k mod (10^9+7).
 *
 * Key identity: sum_{k=1}^{n} F_k = F_{n+2} - 1  (telescoping)
 *
 * Two methods for computing F(n) mod p:
 *   1. Matrix exponentiation:  Q^n gives F(n+1), F(n)  in O(log n)
 *   2. Fast doubling formulas: F(2k) = F(k)(2F(k+1)-F(k)),
 *                              F(2k+1) = F(k)^2 + F(k+1)^2
 */

const long long MOD = 1e9 + 7;

typedef vector<vector<long long>> Matrix;

/* 2x2 matrix multiplication mod p */
Matrix mat_mul(const Matrix& A, const Matrix& B) {
    Matrix C(2, vector<long long>(2, 0));
    for (int i = 0; i < 2; i++)
        for (int k = 0; k < 2; k++)
            for (int j = 0; j < 2; j++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}

/* Matrix binary exponentiation */
Matrix mat_pow(Matrix M, long long n) {
    Matrix R = {{1, 0}, {0, 1}};  // identity
    while (n > 0) {
        if (n & 1) R = mat_mul(R, M);
        M = mat_mul(M, M);
        n >>= 1;
    }
    return R;
}

/* Method 1: F(n) via matrix exponentiation */
long long fib_matrix(long long n) {
    if (n <= 0) return 0;
    if (n <= 2) return 1;
    Matrix Q = {{1, 1}, {1, 0}};
    Matrix R = mat_pow(Q, n - 1);
    return R[0][0];
}

/* Method 2: F(n) via fast doubling - returns (F(n), F(n+1)) */
pair<long long, long long> fib_doubling(long long n) {
    if (n == 0) return {0, 1};
    auto [a, b] = fib_doubling(n >> 1);
    long long c = a % MOD * ((2 * b - a + MOD) % MOD) % MOD;
    long long d = (a % MOD * a % MOD + b % MOD * b % MOD) % MOD;
    if (n & 1)
        return {d, (c + d) % MOD};
    else
        return {c, d};
}

long long fib_fast(long long n) {
    return fib_doubling(n).first;
}

int main() {
    long long N = 10000000;  // 10^7

    // Method 1: matrix
    long long f_mat = fib_matrix(N + 2);
    long long ans1 = (f_mat - 1 + MOD) % MOD;

    // Method 2: fast doubling
    long long f_dbl = fib_fast(N + 2);
    long long ans2 = (f_dbl - 1 + MOD) % MOD;

    assert(ans1 == ans2);

    // Verify small cases
    assert(fib_fast(1) == 1);
    assert(fib_fast(2) == 1);
    assert(fib_fast(10) == 55);
    assert(fib_fast(20) == 6765);

    // Verify telescoping for n=10
    long long sum10 = 0, a = 1, b = 1;
    for (int k = 1; k <= 10; k++) {
        sum10 += a;
        long long t = a;
        a = b;
        b = (t + b);
    }
    assert(sum10 == 143);  // F(12) - 1 = 144 - 1 = 143

    cout << ans1 << endl;
    return 0;
}

"""
Problem 906: Fibonacci Modular Properties

Find sum_{k=1}^{10^7} F_k mod 10^9+7.

Key identity: sum_{k=1}^{n} F_k = F_{n+2} - 1  (telescoping)

Methods:
    1. Matrix exponentiation: O(log n) time
    2. Fast doubling formulas: O(log n) time, no matrix overhead
    3. Iterative: O(n) time (verification for small n)
"""

MOD = 10**9 + 7

def mat_mul(A, B, mod):
    """Multiply 2x2 matrices mod p."""
    return [
        [(A[0][0]*B[0][0] + A[0][1]*B[1][0]) % mod,
         (A[0][0]*B[0][1] + A[0][1]*B[1][1]) % mod],
        [(A[1][0]*B[0][0] + A[1][1]*B[1][0]) % mod,
         (A[1][0]*B[0][1] + A[1][1]*B[1][1]) % mod]
    ]

def mat_pow(M, n, mod):
    """Compute M^n mod p via binary exponentiation."""
    result = [[1, 0], [0, 1]]
    while n > 0:
        if n & 1:
            result = mat_mul(result, M, mod)
        M = mat_mul(M, M, mod)
        n >>= 1
    return result

def fib_matrix(n, mod):
    """Compute F(n) mod p using matrix exponentiation.
    Q^n = [[F(n+1), F(n)], [F(n), F(n-1)]]
    """
    if n <= 0:
        return 0
    if n <= 2:
        return 1
    Q = [[1, 1], [1, 0]]
    R = mat_pow(Q, n - 1, mod)
    return R[0][0]

def fib_doubling(n, mod):
    """Compute (F(n), F(n+1)) mod p using fast doubling.

    F(2k)   = F(k) * (2*F(k+1) - F(k))
    F(2k+1) = F(k)^2 + F(k+1)^2
    """
    if n == 0:
        return (0, 1)

    a, b = fib_doubling(n >> 1, mod)
    c = a * (2 * b - a) % mod
    d = (a * a + b * b) % mod

    if n & 1:
        return (d, (c + d) % mod)
    else:
        return (c, d)

def fib_fast(n, mod):
    """Compute F(n) mod p via fast doubling."""
    return fib_doubling(n, mod)[0]

def fib_sum_iterative(n, mod):
    """Compute sum F(1..n) mod p by iterating."""
    if n <= 0:
        return 0
    total = 0
    a, b = 1, 1  # F(1), F(2)
    for k in range(1, n + 1):
        total = (total + a) % mod
        a, b = b, (a + b) % mod
    return total

# Solve
N = 10**7

fib_np2_mat = fib_matrix(N + 2, MOD)
ans_mat = (fib_np2_mat - 1) % MOD

fib_np2_dbl = fib_fast(N + 2, MOD)
ans_dbl = (fib_np2_dbl - 1) % MOD

assert ans_mat == ans_dbl, f"Mismatch: matrix={ans_mat}, doubling={ans_dbl}"

# Verify telescoping identity for small n
for test_n in [1, 2, 5, 10, 20, 100]:
    s_iter = fib_sum_iterative(test_n, MOD)
    s_formula = (fib_fast(test_n + 2, MOD) - 1) % MOD
    assert s_iter == s_formula, f"n={test_n}: iter={s_iter}, formula={s_formula}"

# Verify known exact values
assert fib_fast(1, MOD) == 1
assert fib_fast(2, MOD) == 1
assert fib_fast(10, MOD) == 55
assert fib_fast(20, MOD) == 6765

print(ans_mat)