Count Good Numbers
WHAT IT SAYS
Count the digit strings of length n where every even index holds an even digit and every odd index holds a prime digit, modulo 1e9+7.
WHAT IT'S REALLY ASKING
"Nothing about position 5 constrains position 6. Each slot independently has 5 legal digits or 4 — so the count is a product, and there is no counting to do at all. The only real difficulty is that n can be 10^15, which means you are not allowed to loop even once per position."
Build the strings, or at least walk the positions
O(10^n) for enumeration; O(n) for the running productThe literal version enumerates the digit strings and tests each one. The sane version walks the n positions and multiplies a running count by 5 or by 4 as it goes, reducing modulo the prime each step.
WHERE THE WORK IS WASTED — Enumeration is obviously hopeless — it rediscovers 10^n times a fact that each position decides for itself, independently. But look at the 'sane' O(n) loop, because its waste is the more interesting one: the body of that loop never changes. It multiplies by 5, then by 5, then by 5, half a quadrillion times. A loop whose body is the same associative operation every iteration is a loop begging to be exponentiated — and with n at 10^15, an O(n) loop is not slow, it is impossible.
Independent slots multiply; identical multiplications compress.
Two steps, and each one deletes an entire dimension of work. Step one: the constraint on position i mentions only position i. There is no rule connecting neighbours, no rule about the string as a whole. So the good numbers are exactly the cartesian product of the per-position legal sets, and the size of a product is the product of the sizes. Even indices take one of {0,2,4,6,8} — five options. Odd indices take one of {2,3,5,7} — four options. With 0-indexing there are ceil(n/2) even positions and floor(n/2) odd ones, so the answer is 5^ceil(n/2) times 4^floor(n/2). That is not an algorithm. It is an identity, and it contains no enumeration whatsoever. Step two: you are now left with exponentiation, and the exponent is astronomical. But multiplication is associative, so a^b can be computed by repeated squaring — each squaring HALVES the exponent, and an integer can only be halved log2(b) times. Fifty-ish multiplications, not a quadrillion. And modular arithmetic survives all of it, because multiplication commutes with taking the remainder: (a * b) mod p equals ((a mod p) * (b mod p)) mod p. So you may reduce after every single step and never let a number grow. Keep the intermediates in 64 bits — two values below 1e9 multiply to under 1e18, which still fits — and the arithmetic never overflows.
Two fast powers, multiplied
O(log n) time, O(1) spaceReturn powmod(5, (n+1)/2) times powmod(4, n/2), modulo 1e9+7, where powmod squares the base and spends the set bits of the exponent. Two logarithmic loops and one multiplication — the whole solution.
Count, Don't Enumerate
YOU'LL SEE IT AGAIN WHEN
- The constraints are per-position and independent, so the count is a product of per-position option counts rather than a search.
- n is astronomically large (1e9 and up), which forbids any O(n) loop outright and points at a closed form or a logarithmic one.
- The loop body is the same associative operation on every iteration — which means repeated squaring can compress it.