Problem 709: Even Stevens

Mathematical Foundation

Theorem 1 (Recurrence for $p(n)$). The probability $p(n)$ satisfies

with initial conditions $p(0) = 1$ and $p(1) = \frac{1}{2}$.

Proof. To land exactly on $n$, the last step must arrive at $n$ from either $n-1$ (via heads) or $n-2$ (via tails). If the player is at score $n-1$, flipping heads (probability $\frac{1}{2}$) reaches $n$ exactly. If at score $n-2$, flipping tails (probability $\frac{1}{2}$) reaches $n$ exactly. Thus $p(n) = \frac{1}{2}\,p(n-1) + \frac{1}{2}\,p(n-2)$.

For the base cases: $p(0) = 1$ (the player starts at 0 with certainty). $p(1) = \frac{1}{2}\,p(0) = \frac{1}{2}$ (the only way to reach exactly 1 is to flip heads from 0). $\square$

Theorem 2 (Closed Form). For $n \ge 0$,

Proof. The characteristic equation of $p(n) = \frac{1}{2}\,p(n-1) + \frac{1}{2}\,p(n-2)$ is $2x^2 - x - 1 = 0$, which factors as $(2x + 1)(x - 1) = 0$. The roots are $x = 1$ and $x = -\frac{1}{2}$.

The general solution is $p(n) = A \cdot 1^n + B \cdot (-\frac{1}{2})^n = A + B(-\frac{1}{2})^n$.

Applying initial conditions:

• $p(0) = 1$: $A + B = 1$.
• $p(1) = \frac{1}{2}$: $A - \frac{B}{2} = \frac{1}{2}$.

From the first equation, $B = 1 - A$. Substituting into the second: $A - (1-A)/2 = 1/2$, so $3A/2 = 1$, giving $A = 2/3$ and $B = 1/3$. $\square$

Theorem 3 (Closed Form for the Sum). Define $\Sigma(N) = \sum_{n=1}^{N} p(n)$. Then

Proof.

The geometric sum is $\sum_{n=1}^{N} r^n = r(1 - r^N)/(1 - r)$ with $r = -1/2$:

Therefore $\Sigma(N) = \frac{2N}{3} - \frac{1}{9}(1 - (-\frac{1}{2})^N)$. $\square$

Lemma 1 (Modular Arithmetic). To compute $\Sigma(N) \bmod p$ where $p = 10^9 + 7$:

• $2/3 \bmod p$: compute $2 \cdot 3^{p-2} \bmod p$.
• $(-1/2)^N \bmod p$: compute $(-1)^N \cdot (2^{p-2})^N \bmod p = (-1)^N \cdot 2^{N(p-2) \bmod (p-1)} \bmod p$.
• $1/9 \bmod p$: compute $9^{p-2} \bmod p$.

Proof. Since $p$ is prime and $\gcd(2, p) = \gcd(3, p) = \gcd(9, p) = 1$, all modular inverses exist by Fermat’s little theorem. $\square$

Editorial

We 2N/3 mod p. We then (-1/2)^N mod p. Finally, else. We enumerate the admissible parameter range, discard candidates that violate the derived bounds or arithmetic constraints, and update the final set or total whenever a candidate passes the acceptance test.

Pseudocode

p = 10^9 + 7
2N/3 mod p
(-1/2)^N mod p
if N is even
else
1/9 * (1 - (-1/2)^N) mod p
Note: be careful with sign: we subtract term2
Sigma = term1 - term2
But (-1/2)^N for modular: pow(-inv2, N, p) = pow(p - inv2, N, p)

Complexity Analysis

• Time: $O(\log N)$ for modular exponentiation. All other operations are $O(1)$.
• Space: $O(1)$.

Answer

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
long long power(long long a, long long b, long long mod) {
    long long res = 1; a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
int main() {
    long long N = 10000000;
    long long inv2 = power(2, MOD - 2, MOD);
    long long inv3 = power(3, MOD - 2, MOD);
    long long two_N_3 = 2 * N % MOD * inv3 % MOD;
    long long neg_half = (MOD - inv2) % MOD;
    long long neg_half_N = power(neg_half, N, MOD);
    long long geo = (MOD - 1 + MOD) % MOD * ((1 - neg_half_N + MOD) % MOD) % MOD * inv3 % MOD;
    long long ans = (two_N_3 + inv3 % MOD * geo % MOD) % MOD;
    cout << ans << endl;
    return 0;
}

"""
Problem 709: Even Stevens
"""

def solve():
    MOD = 10**9 + 7
    N = 10**7
    inv2 = pow(2, MOD - 2, MOD)
    inv3 = pow(3, MOD - 2, MOD)

    # p(n) = 2/3 + (1/3)(-1/2)^n
    # sum_{n=1}^{N} p(n) = 2N/3 + (1/3) * sum_{n=1}^{N} (-1/2)^n
    # Geometric sum: sum = (-1/2)(1 - (-1/2)^N) / (1 - (-1/2)) = (-1/2)(1-(-1/2)^N)/(3/2)
    # = -(1-(-1/2)^N)/3

    two_N_over_3 = 2 * N % MOD * inv3 % MOD

    # (-1/2)^N mod MOD
    neg_half = MOD - inv2  # -1/2 mod MOD
    neg_half_N = pow(neg_half, N, MOD)

    geo_sum = (MOD - 1) * (1 - neg_half_N + MOD) % MOD * inv3 % MOD

    result = (two_N_over_3 + inv3 * geo_sum) % MOD
    return result

answer = solve()
print(answer)