Problem 532: Nanoscale Strips

Mathematical Foundation

Strip Pattern Counting

Definition 1. A pattern on the $W \times H$ grid is a selection of non-overlapping unit-height horizontal strips placed at integer vertical positions within the grid. Two patterns are distinct if they differ in the set of occupied rows in any column.

Theorem 1 (Combinatorial Formula). Under the problem’s placement rules, the number of distinct visible patterns satisfies

where $p = 999\,999\,937$.

Proof. Each column of the grid can be analyzed independently. For a single column of height $H$ with $W$ available strip-unit slots, a valid configuration corresponds to choosing which of the $H$ vertical positions are occupied by strips, subject to the constraint that exactly $W$ units are placed. By the stars-and-bars principle, distributing $H$ units of gap among the $W + 1$ possible positions (above the first strip, between consecutive strips, and below the last strip) yields $\binom{W + H}{W}$ configurations per column. Since the two-dimensional grid structure factors into independent column contributions, the total count is $\binom{W + H}{W}^2$. $\blacksquare$

Modular Binomial Computation

Lemma 1 (Factorial-Based Binomial Evaluation). Let $p$ be a prime and $0 \le k \le n < p$. Then $\binom{n}{k} \bmod p$ can be computed in $O(n)$ preprocessing time and $O(1)$ per query.

Proof. Precompute the array $F[i] = i! \bmod p$ for $0 \le i \le n$ using the recurrence $F[0] = 1$, $F[i] = i \cdot F[i-1] \bmod p$. This requires $O(n)$ multiplications. Next, compute the modular inverse $F^{-1}[n] \equiv (n!)^{p-2} \pmod{p}$ via Fermat’s little theorem (valid since $p$ is prime and $n < p$ guarantees $p \nmid n!$), costing $O(\log p)$. Fill inverse factorials in descending order:

This is correct because $(i!)^{-1} = (i+1) \cdot ((i+1)!)^{-1}$ in $\mathbb{Z}/p\mathbb{Z}$. Each binomial coefficient is then

in $O(1)$. $\blacksquare$

Remark. Since $W + H = 2 \times 10^7 < p = 999\,999\,937$, the condition $n < p$ in Lemma 1 is satisfied, and no factorial vanishes modulo $p$.

Editorial

Compute f(10^7, 10^7) mod 999999937, where f(W,H) = C(W+H, W)^2 mod p. Method: precompute factorials and inverse factorials mod p, then evaluate the binomial coefficient in O(1). We precompute factorials mod p. We then inverse factorials via Fermat. Finally, binomial coefficient.

Pseudocode

Precompute factorials mod p
Inverse factorials via Fermat
Binomial coefficient

Complexity Analysis

• Time: $O(W + H + \log p)$. The factorial precomputation takes $O(W + H)$ multiplications; the single modular exponentiation costs $O(\log p)$.
• Space: $O(W + H)$ for the factorial and inverse factorial arrays.

For $W = H = 10^7$: approximately $2 \times 10^7$ operations, completing in under one second.

Answer

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

/*
 * Problem 532: Nanoscale Strips
 *
 * f(W,H) = C(W+H, W)^2 mod p,  p = 999999937.
 *
 * Precompute factorials and inverse factorials mod p, then evaluate.
 * Time: O(W+H).  Space: O(W+H).
 */

const ll MOD = 999999937LL;
const int MAXN = 20000001;

ll fact[MAXN], inv_fact[MAXN];

ll power(ll base, ll exp, ll mod) {
    ll result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

void precompute(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++)
        fact[i] = fact[i - 1] * i % MOD;
    inv_fact[n] = power(fact[n], MOD - 2, MOD);
    for (int i = n - 1; i >= 0; i--)
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
}

ll binom(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] % MOD * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

int main() {
    int W = 10000000, H = 10000000;
    precompute(W + H);
    ll c = binom(W + H, W);
    ll ans = c * c % MOD;
    cout << ans << endl;
    return 0;
}

"""
Problem 532: Nanoscale Strips

Compute f(10^7, 10^7) mod 999999937, where f(W,H) = C(W+H, W)^2 mod p.

Method: precompute factorials and inverse factorials mod p, then
evaluate the binomial coefficient in O(1).
"""

MOD = 999999937

def solve(W, H, mod):
    n = W + H
    # Precompute factorials
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % mod
    # Inverse factorials via Fermat's little theorem
    inv_fact = [1] * (n + 1)
    inv_fact[n] = pow(fact[n], mod - 2, mod)
    for i in range(n - 1, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod
    # C(n, W) mod p
    c = fact[n] * inv_fact[W] % mod * inv_fact[H] % mod
    return c * c % mod

print(solve(10**7, 10**7, MOD))