Problem 490: Jumping Frog

Mathematical Foundation

Theorem 1 (Tribonacci recurrence). Let $f(k)$ denote the number of distinct paths from stone 0 to stone $k$. Then

with initial conditions $f(0) = 1$, $f(1) = 1$, $f(2) = 2$.

Proof. To reach stone $k$, the frog’s last jump was of size 1, 2, or 3, arriving from stone $k-1$, $k-2$, or $k-3$ respectively. These three cases are mutually exclusive and exhaustive (every path to $k$ ends with one of these three jumps). Therefore $f(k) = f(k-1) + f(k-2) + f(k-3)$.

For the initial conditions: $f(0) = 1$ (the empty path from 0 to 0). $f(1) = 1$ (one path: jump of 1). $f(2) = 2$ (two paths: $0 \to 1 \to 2$ and $0 \to 2$). Verification: $f(3) = f(2) + f(1) + f(0) = 2 + 1 + 1 = 4$ (the paths $0\to1\to2\to3$, $0\to2\to3$, $0\to1\to3$, $0\to3$). $\square$

Theorem 2 (Matrix exponentiation). The recurrence can be expressed in matrix form:

Therefore, for $n \ge 2$:

Proof. The matrix form is a direct restatement of the recurrence. The power formula follows by induction: if the relation holds for $k$, applying $A$ once more gives the relation for $k+1$. $\square$

Theorem 3 (Generating function). The ordinary generating function of the sequence $\{f(k)\}_{k \ge 0}$ is

Proof. Multiply both sides of the recurrence $f(k) = f(k-1) + f(k-2) + f(k-3)$ by $x^k$ and sum for $k \ge 3$:

Using $F(x) = \sum_{k \ge 0} f(k)x^k$ and separating the first few terms:

Substituting $f(0) = 1, f(1) = 1, f(2) = 2$:

Solving: $F(x)(1 - x - x^2 - x^3) = 1$, hence $F(x) = 1/(1 - x - x^2 - x^3)$. $\square$

Lemma 1 (Asymptotic growth). The dominant root of the characteristic equation $x^3 = x^2 + x + 1$ (equivalently $x^3 - x^2 - x - 1 = 0$) is the tribonacci constant

Therefore $f(n) \sim C \cdot \tau^n$ as $n \to \infty$ for some constant $C > 0$.

Proof. The characteristic polynomial $p(x) = x^3 - x^2 - x - 1$ has $p(1) = -2 < 0$ and $p(2) = 1 > 0$, so there is a real root $\tau \in (1, 2)$. By Descartes’ rule, $p(x)$ has exactly one positive real root. The other two roots are complex conjugates with modulus less than $\tau$ (since $|r| < \tau$ for the complex roots, which can be verified from Vieta’s formulas: the product of all three roots is 1, so the product of the complex pair is $1/\tau < 1$, meaning their common modulus is $\tau^{-1/2} < 1 < \tau$). Thus the dominant term in the closed form is $C \tau^n$. $\square$

Editorial

A frog jumps on stepping stones 0..n, jumping 1, 2, or 3 steps forward. Count the number of distinct paths from 0 to n. Uses tribonacci recurrence and matrix exponentiation. We o(n) time, O(1) space. Finally, o(log n) time, O(1) space.

Pseudocode

O(n) time, O(1) space
O(log n) time, O(1) space
f(n) = result[0][0]*2 + result[0][1]*1 + result[0][2]*1
if exp is odd

Complexity Analysis

• Time (DP): $O(n)$. Each step performs 3 additions.
• Space (DP): $O(1)$. Only the last 3 values are stored.
• Time (Matrix exponentiation): $O(3^3 \log n) = O(27 \log n) = O(\log n)$. Each matrix multiplication is $O(27)$ for $3 \times 3$ matrices, and $O(\log n)$ squarings are needed.
• Space (Matrix exponentiation): $O(3^2) = O(1)$. A constant number of $3 \times 3$ matrices.

Answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> Matrix;

const ll MOD = 1e9 + 7;

Matrix mat_mult(const Matrix& A, const Matrix& B) {
    int n = A.size();
    Matrix C(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++) if (A[i][k])
            for (int j = 0; j < n; j++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}

Matrix mat_pow(Matrix M, ll p) {
    int n = M.size();
    Matrix result(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++) result[i][i] = 1; // identity
    while (p > 0) {
        if (p & 1) result = mat_mult(result, M);
        M = mat_mult(M, M);
        p >>= 1;
    }
    return result;
}

ll solve(ll n) {
    if (n == 0) return 1;
    if (n == 1) return 1;
    if (n == 2) return 2;

    Matrix A = {{1, 1, 1}, {1, 0, 0}, {0, 1, 0}};
    Matrix An = mat_pow(A, n - 2);
    // f(n) = An[0][0]*f(2) + An[0][1]*f(1) + An[0][2]*f(0)
    return (An[0][0] * 2 + An[0][1] + An[0][2]) % MOD;
}

int main() {
    // Print first few values
    cout << "Frog jumping paths f(n):" << endl;
    for (int n = 0; n <= 20; n++) {
        cout << "f(" << n << ") = " << solve(n) << endl;
    }

    // Large value
    ll big = 1000000000000000000LL;
    cout << "\nf(10^18) mod 10^9+7 = " << solve(big) << endl;

    return 0;
}

"""
Problem 490: Jumping Frog
A frog jumps on stepping stones 0..n, jumping 1, 2, or 3 steps forward.
Count the number of distinct paths from 0 to n.
Uses tribonacci recurrence and matrix exponentiation.
"""

def solve_dp(n: int, mod: int = 0):
    """Count paths using DP (tribonacci recurrence). O(n) time."""
    if n == 0:
        return 1
    if n == 1:
        return 1
    if n == 2:
        return 2

    a, b, c = 1, 1, 2  # f(0), f(1), f(2)
    for _ in range(3, n + 1):
        a, b, c = b, c, (a + b + c) if mod == 0 else (a + b + c) % mod
    return c

def mat_mult(A: list, B: list, mod: int) -> list:
    """Multiply two 3x3 matrices modulo mod."""
    n = len(A)
    C = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            s = 0
            for k in range(n):
                s += A[i][k] * B[k][j]
            C[i][j] = s % mod if mod else s
    return C

def mat_pow(M: list, p: int, mod: int) -> list:
    """Compute M^p mod mod using exponentiation by squaring."""
    n = len(M)
    # Identity matrix
    result = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
    base = [row[:] for row in M]
    while p > 0:
        if p & 1:
            result = mat_mult(result, base, mod)
        base = mat_mult(base, base, mod)
        p >>= 1
    return result

def solve_matrix(n: int, mod: int = 10**9 + 7):
    """Count paths using matrix exponentiation. O(log n) time."""
    if n == 0:
        return 1
    if n == 1:
        return 1
    if n == 2:
        return 2 % mod

    A = [[1, 1, 1],
         [1, 0, 0],
         [0, 1, 0]]

    An = mat_pow(A, n, mod)
    # f(n) = An[0][0]*f(0) + An[0][1]*f(-1) + An[0][2]*f(-2)
    # But we use: (f(n), f(n-1), f(n-2)) = A^(n-2) * (f(2), f(1), f(0))
    An2 = mat_pow(A, n - 2, mod)
    result = (An2[0][0] * 2 + An2[0][1] * 1 + An2[0][2] * 1) % mod
    return result

def solve_dp_with_forbidden(n: int, forbidden: set):
    """Count paths avoiding forbidden stones."""
    f = [0] * (n + 1)
    f[0] = 1
    for k in range(1, n + 1):
        if k in forbidden:
            f[k] = 0
        else:
            f[k] = sum(f[k - j] for j in [1, 2, 3] if k - j >= 0)
    return f[n]

# Verify: DP vs matrix
mod = 10**9 + 7
for n in range(20):
    dp_val = solve_dp(n, mod)
    mat_val = solve_matrix(n, mod)
    assert dp_val == mat_val, f"Mismatch at n={n}: {dp_val} vs {mat_val}"

print("Verification passed for n=0..19")

# Show first values
print("\nPaths f(n) for n=0..20:")
for n in range(21):
    print(f"  f({n:2d}) = {solve_dp(n)}")

# Large n example
large_n = 10**18
print(f"\nf({large_n}) mod 10^9+7 = {solve_matrix(large_n, mod)}")

# Forbidden stones example
print(f"\nPaths from 0 to 10 avoiding stones {{3, 7}}: {solve_dp_with_forbidden(10, {3, 7})}")