| F(n+1)  F(n)   |     | 1  1 |^n
| F(n)    F(n-1) |  =  | 1  0 |

Matriz base M = | 1  1 |
                | 1  0 |

M^1 = | 1  1 |  → F(2)=1, F(1)=1
      | 1  0 |

M^2 = | 2  1 |  → F(3)=2, F(2)=1
      | 1  1 |

M^4 = M^2 × M^2 = | 5  3 |  → F(5)=5, F(4)=3
                   | 3  2 |

M^8 = M^4 × M^4 = | 34  21 |  → F(9)=34, F(8)=21
                   | 21  13 |

Para F(10): M^10 = M^8 × M^2
                 = | 89  55 |  → F(10) = 55 ✓
                   | 55  34 |

Apenas 4 multiplicações de matrizes para F(10)!

const std = @import("std");

const MOD: u64 = 1_000_000_007;

/// Matriz 2x2 para Fibonacci.
const Mat2 = [2][2]u64;

const IDENTIDADE: Mat2 = .{ .{ 1, 0 }, .{ 0, 1 } };
const FIB_BASE: Mat2 = .{ .{ 1, 1 }, .{ 1, 0 } };

/// Multiplica duas matrizes 2x2 com módulo.
fn matMul(a: Mat2, b: Mat2) Mat2 {
    var resultado: Mat2 = undefined;
    for (0..2) |i| {
        for (0..2) |j| {
            var soma: u128 = 0;
            for (0..2) |k| {
                soma += @as(u128, a[i][k]) * @as(u128, b[k][j]);
            }
            resultado[i][j] = @intCast(soma % MOD);
        }
    }
    return resultado;
}

/// Exponenciação rápida de matriz 2x2 — O(log n).
fn matPow(mat: Mat2, n: u64) Mat2 {
    if (n == 0) return IDENTIDADE;

    var resultado = IDENTIDADE;
    var base = mat;
    var exp = n;

    while (exp > 0) {
        if (exp & 1 == 1) {
            resultado = matMul(resultado, base);
        }
        base = matMul(base, base);
        exp >>= 1;
    }
    return resultado;
}

/// Calcula F(n) mod 10^9+7 em O(log n).
pub fn fibonacci(n: u64) u64 {
    if (n == 0) return 0;
    if (n <= 2) return 1;

    const resultado = matPow(FIB_BASE, n - 1);
    return resultado[0][0];
}

/// Calcula F(n) sem módulo (para números pequenos).
pub fn fibonacciSemMod(n: u64) u64 {
    if (n == 0) return 0;
    if (n <= 2) return 1;

    var resultado: [2][2]u64 = .{ .{ 1, 0 }, .{ 0, 1 } };
    var base: [2][2]u64 = .{ .{ 1, 1 }, .{ 1, 0 } };
    var exp = n - 1;

    while (exp > 0) {
        if (exp & 1 == 1) {
            var temp: [2][2]u64 = undefined;
            for (0..2) |i| {
                for (0..2) |j| {
                    temp[i][j] = 0;
                    for (0..2) |k| {
                        temp[i][j] += resultado[i][k] * base[k][j];
                    }
                }
            }
            resultado = temp;
        }
        var temp: [2][2]u64 = undefined;
        for (0..2) |i| {
            for (0..2) |j| {
                temp[i][j] = 0;
                for (0..2) |k| {
                    temp[i][j] += base[i][k] * base[k][j];
                }
            }
        }
        base = temp;
        exp >>= 1;
    }
    return resultado[0][0];
}

/// Identidades úteis de Fibonacci:
/// F(2n) = F(n) * (2*F(n+1) - F(n))
/// F(2n+1) = F(n)^2 + F(n+1)^2
/// (Fast doubling — ainda O(log n) mas sem multiplicação de matrizes)
pub fn fibFastDoubling(n: u64) [2]u64 {
    if (n == 0) return .{ 0, 1 }; // {F(0), F(1)}

    const pair = fibFastDoubling(n >> 1);
    const fn_val = pair[0];
    const fn1 = pair[1];

    // F(2k) = F(k) * (2*F(k+1) - F(k))
    const c = (fn_val % MOD) * ((2 * fn1 % MOD + MOD - fn_val % MOD) % MOD) % MOD;
    // F(2k+1) = F(k)^2 + F(k+1)^2
    const d = ((fn_val % MOD) * (fn_val % MOD) + (fn1 % MOD) * (fn1 % MOD)) % MOD;

    if (n & 1 == 0) {
        return .{ c, d };
    } else {
        return .{ d, (c + d) % MOD };
    }
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();

    // Primeiros termos
    try stdout.print("=== Fibonacci (Exponenciação de Matriz) ===\n", .{});
    try stdout.print("Primeiros 20 termos:\n", .{});
    for (0..20) |i| {
        try stdout.print("F({d}) = {d}\n", .{ i, fibonacciSemMod(@intCast(i)) });
    }

    // Termos grandes (mod 10^9+7)
    try stdout.print("\n=== Termos grandes (mod 10^9+7) ===\n", .{});
    const grandes = [_]u64{ 100, 1_000, 1_000_000, 1_000_000_000 };
    for (grandes) |n| {
        try stdout.print("F({d}) mod 10^9+7 = {d}\n", .{ n, fibonacci(n) });
    }

    // Fast doubling
    try stdout.print("\n=== Fast Doubling ===\n", .{});
    for ([_]u64{ 10, 100, 1000 }) |n| {
        const result = fibFastDoubling(n);
        try stdout.print("F({d}) mod 10^9+7 = {d}\n", .{ n, result[0] });
    }
}

n = 10^18:
  DP iterativo:  ~10^18 operações — IMPRATICÁVEL
  Matriz/doubling: ~60 operações — INSTANTÂNEO