Problem 322: Binomial Coefficients Divisible by 10

Solution

Inclusion—exclusion via Lucas’ theorem

Theorem 1 (Lucas). Let $p$ be a prime. Write $i = \sum_j i_j p^j$ and $n = \sum_j n_j p^j$ in base $p$. Then

Corollary 1. $\binom{i}{n} \not\equiv 0 \pmod{p}$ if and only if $i_j \geq n_j$ for every digit position $j$ (digit-wise domination).

Proof. Each factor $\binom{i_j}{n_j}$ is nonzero in $\mathbb{F}_p$ if and only if $i_j \geq n_j$. The product vanishes if and only if at least one factor vanishes. $\square$

Definition 1. For a prime $p$, let

For the composite modulus $10 = 2 \times 5$, let

Theorem 2 (Inclusion—exclusion). Since $10 = 2 \times 5$ with $\gcd(2,5)=1$,

Proof. For each $i \in [n, m)$, define events $A = \{2 \mid \binom{i}{n}\}$ and $B = \{5 \mid \binom{i}{n}\}$. Then $10 \mid \binom{i}{n}$ iff $A \cap B$ holds. By inclusion—exclusion,

where $\overline{|A|} = f_2$, $\overline{|B|} = f_5$, and $\overline{|A \cup B|} = f_{10}$. Equivalently, $T = (m-n) - f_2 - f_5 + f_{10}$. $\square$

Single-prime digit DP

Proposition 1. For a prime $p$, $f_p(m, n)$ equals the number of integers $i \in [0, m)$ whose base-$p$ digits dominate those of $n$ position-by-position, minus 1 if $m$ itself satisfies the domination condition. This count is evaluated by a standard digit DP on the base-$p$ representation of $m$, processing digits from the most significant to the least significant, with a single boolean state recording whether the prefix constructed so far equals that of $m$ (tight) or is strictly less (free).

Proof. By Corollary 1, $p \nmid \binom{i}{n}$ iff every base-$p$ digit of $i$ is at least the corresponding digit of $n$. The digit DP correctly enumerates all such $i$ in $[0, m)$ by enforcing digit-wise constraints: at each position $j$, the chosen digit $d_j$ satisfies $n_j \leq d_j \leq u_j$ where $u_j = m_j$ if the prefix is tight, and $u_j = p - 1$ otherwise. $\square$

Joint digit DP for $f_{10}$

Theorem 3. When $m = 10^K$, the count $f_{10}(m, n)$ is computed by a DP in base 10. At digit position $k$ (from the least significant), the state is a pair $(c_2, c_5)$ of carry values encoding the partially computed base-2 and base-5 representations of $i$. For a base-10 digit $d \in \{0, \ldots, 9\}$ at position $k$:

The digit is accepted only if both extracted base-$p$ digits dominate the corresponding digits of $n$. After all $K$ positions, the final carries must also satisfy domination for any remaining high-order digits of $n$.

Proof. Since $10^k = 2^k \cdot 5^k$, each base-10 digit $d$ at position $k$ contributes $d \cdot 5^k$ to the base-2 representation (after factoring out powers of 2) and $d \cdot 2^k$ to the base-5 representation (after factoring out powers of 5). The carry variables $c_2$ and $c_5$ track the values $\lfloor (\text{partial sum}) / 2^{k}\rfloor$ and $\lfloor (\text{partial sum}) / 5^{k}\rfloor$ needed to reconstruct higher-order digits. Since $5^k$ is always odd, $(c_2 + d) \bmod 2$ gives the correct base-2 digit at position $k$. The domination constraint from Corollary 1 is enforced digit by digit. $\square$

Editorial

T(m, n) = #{i in [n, m) : 10 | C(i, n)}. By inclusion-exclusion on primes 2 and 5: T = (m - n) - f_2 - f_5 + f_10 where f_p counts i with p not dividing C(i,n) (digit-wise domination in base p). f_10 uses a joint base-10 digit DP tracking carry states for base-2 and base-5.

Pseudocode

    f2 = digit_dp_single_prime(m, n, 2)
    f5 = digit_dp_single_prime(m, n, 5)
    f10 = joint_digit_dp_base10(K = log10(m), n)
    Return (m - n) - f2 - f5 + f10

Complexity

• Time: $O(L_2)$ for $f_2$, $O(L_5)$ for $f_5$ (where $L_p$ is the number of base-$p$ digits of $m$), and $O(K \cdot |S| \cdot 10)$ for $f_{10}$ where $|S|$ is the number of reachable carry states. Dominant term: $O(K \cdot |S|)$.
• Space: $O(|S|)$ per DP layer.

Answer

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

vector<int> to_base(ll x, int p) {
    if (x == 0) return {0};
    vector<int> d;
    while (x > 0) { d.push_back(x % p); x /= p; }
    return d;
}

ll count_geq_digits(ll m, ll n, int p) {
    auto nd = to_base(n, p), md = to_base(m, p);
    int L = max(nd.size(), md.size());
    nd.resize(L, 0);
    md.resize(L, 0);
    reverse(nd.begin(), nd.end());
    reverse(md.begin(), md.end());

    vector<ll> dp(2, 0);
    dp[1] = 1;
    for (int pos = 0; pos < L; pos++) {
        vector<ll> ndp(2, 0);
        for (int t = 0; t < 2; t++) {
            if (!dp[t]) continue;
            int upper = t ? md[pos] : (p - 1);
            for (int d = nd[pos]; d <= upper; d++) {
                int nt = t && (d == md[pos]) ? 1 : 0;
                ndp[nt] += dp[t];
            }
        }
        dp = ndp;
    }
    ll res = dp[0] + dp[1];
    bool all_ok = true;
    for (int j = 0; j < L; j++)
        if (md[j] < nd[j]) { all_ok = false; break; }
    if (all_ok) res--;
    return res;
}

ll count_f10(ll m, ll n) {
    auto n2 = to_base(n, 2), n5 = to_base(n, 5);
    int K = (int)round(log10((double)m));

    ll n_high2 = n >> K;
    ll p5k = 1;
    for (int i = 0; i < K; i++) p5k *= 5;
    ll n_high5 = n / p5k;

    map<pll, ll> states;
    states[{0, 0}] = 1;
    ll pow5 = 1, pow2 = 1;

    for (int k = 0; k < K; k++) {
        map<pll, ll> ns;
        int n2k = (k < (int)n2.size()) ? n2[k] : 0;
        int n5k = (k < (int)n5.size()) ? n5[k] : 0;
        for (auto &[st, cnt] : states) {
            ll c2 = st.first, c5 = st.second;
            for (int d = 0; d < 10; d++) {
                if ((int)((c2 + d) % 2) < n2k) continue;
                if ((int)((c5 + d * pow2) % 5) < n5k) continue;
                ll nc2 = (c2 + d * pow5) / 2;
                ll nc5 = (c5 + d * pow2) / 5;
                ns[{nc2, nc5}] += cnt;
            }
        }
        states = ns;
        pow5 *= 5;
        pow2 *= 2;
    }

    ll total = 0;
    for (auto &[st, cnt] : states) {
        ll c2 = st.first, c5 = st.second;
        if (n_high2 > 0 && (c2 & n_high2) != n_high2) continue;
        if (n_high5 > 0) {
            auto nh = to_base(n_high5, 5), ch = to_base(c5, 5);
            bool ok = true;
            for (int j = 0; j < (int)nh.size(); j++) {
                int cj = (j < (int)ch.size()) ? ch[j] : 0;
                if (cj < nh[j]) { ok = false; break; }
            }
            if (!ok) continue;
        }
        total += cnt;
    }
    return total;
}

int main() {
    ll m = 1000000000000000000LL;
    ll n = 999999999990LL;
    ll f2 = count_geq_digits(m, n, 2);
    ll f5 = count_geq_digits(m, n, 5);
    ll f10 = count_f10(m, n);
    cout << (m - n) - f2 - f5 + f10 << endl;
    return 0;
}

"""
Problem 322: Binomial Coefficients Divisible by 10

T(m, n) = #{i in [n, m) : 10 | C(i, n)}.
By inclusion-exclusion on primes 2 and 5:
    T = (m - n) - f_2 - f_5 + f_10
where f_p counts i with p not dividing C(i,n) (digit-wise domination in base p).
f_10 uses a joint base-10 digit DP tracking carry states for base-2 and base-5.
"""
import math
from functools import lru_cache


def to_base(x, p):
    if x == 0:
        return [0]
    d = []
    while x > 0:
        d.append(x % p)
        x //= p
    return d


def count_geq_digits(m, n, p):
    """Count i in [0, m) with every base-p digit of i >= that of n."""
    nd = to_base(n, p)
    md = to_base(m, p)
    L = max(len(nd), len(md))
    nd += [0] * (L - len(nd))
    md += [0] * (L - len(md))
    nd_r = nd[::-1]
    md_r = md[::-1]

    @lru_cache(maxsize=None)
    def dp(pos, tight):
        if pos == L:
            return 1
        upper = md_r[pos] if tight else (p - 1)
        lower = nd_r[pos]
        if lower > upper:
            return 0
        total = 0
        for d in range(lower, upper + 1):
            total += dp(pos + 1, tight and (d == md_r[pos]))
        return total

    result = dp(0, True)
    # Exclude i = m (we want [0, m), and dp counts [0, m])
    if all(md_r[j] >= nd_r[j] for j in range(L)):
        result -= 1
    return result


def count_f10_dp(m, n):
    """Count i in [0, m) with gcd(C(i,n), 10) = 1, via base-10 digit DP."""
    n2 = to_base(n, 2)
    n5 = to_base(n, 5)
    K = round(math.log10(m))
    assert 10**K == m

    n_high2 = n >> K
    n_high5 = n // (5**K)

    def check_end(c2, c5):
        if n_high2 > 0 and (c2 & n_high2) != n_high2:
            return False
        if n_high5 > 0:
            nh5d = to_base(n_high5, 5)
            c5d = to_base(c5, 5) if c5 > 0 else [0]
            for j in range(len(nh5d)):
                cj = c5d[j] if j < len(c5d) else 0
                if cj < nh5d[j]:
                    return False
        return True

    states = {(0, 0): 1}
    pow5, pow2 = 1, 1

    for k in range(K):
        new_states = {}
        n2k = n2[k] if k < len(n2) else 0
        n5k = n5[k] if k < len(n5) else 0

        for (c2, c5), cnt in states.items():
            for d in range(10):
                b2 = (c2 + d) % 2
                if b2 < n2k:
                    continue
                b5 = (c5 + d * pow2) % 5
                if b5 < n5k:
                    continue
                nc2 = (c2 + d * pow5) // 2
                nc5 = (c5 + d * pow2) // 5
                key = (nc2, nc5)
                new_states[key] = new_states.get(key, 0) + cnt

        states = new_states
        pow5 *= 5
        pow2 *= 2

    total = 0
    for (c2, c5), cnt in states.items():
        if check_end(c2, c5):
            total += cnt
    return total


def solve():
    m = 10**18
    n = 10**12 - 10
    f2 = count_geq_digits(m, n, 2)
    f5 = count_geq_digits(m, n, 5)
    f10 = count_f10_dp(m, n)
    print((m - n) - f2 - f5 + f10)


if __name__ == "__main__":
    solve()