Intermission, the Sequel - Java Solution

import java.io.IOException;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.Map;

import com.google.auto.value.AutoValue;
import com.google.common.base.Preconditions;
import com.google.common.collect.Maps;

public class Brilliant {

    @AutoValue
    abstract static class PArgs {
        public static PArgs make(int N, int k, int q) {
            return new AutoValue_Brilliant_PArgs(N, k, q);
        }
        public abstract int N();
        public abstract int k();
        public abstract int q();
    }

    private static final Map<PArgs, BigDecimal> PCACHE = new HashMap<>();
    private static final BigDecimal TAILS = new BigDecimal("0.01");
    private static final BigDecimal HEADS = BigDecimal.ONE.subtract(TAILS);

    // P of at least k consecutive heads, and at most q tails in exactly N flips
    private static BigDecimal P(int N, int k, int q) {
        Preconditions.checkArgument(N >= 0);
        Preconditions.checkArgument(k >= 0);
        Preconditions.checkArgument(q >= 0);
        PArgs args = PArgs.make(N, k, q);
        if (PCACHE.containsKey(args)) return PCACHE.get(args);

        BigDecimal ret;
        if (N == 0) {
            ret = (k == 0) ? BigDecimal.ONE : BigDecimal.ZERO;
        } else if (N == k) {
            ret = HEADS.pow(N);
        } else if (q == 0) {
            ret = (N < k) ? BigDecimal.ZERO : HEADS.pow(N);
        } else if (k == 0) {
            ret = HEADS.multiply(P(N-1, 0, q)).add(TAILS.multiply(P(N-1, 0, q-1)));
        } else if (N < k) {
            ret = BigDecimal.ZERO;
        } else {
            ret = TAILS.multiply(P(N-1, k, q-1)).add(HEADS.multiply(P(N-1, k, q)));

            // Opposite case:  Got max k-1 or less consecutive heads in N-k-1 coins, with at most q-1 tails
            // Then, got tails, and then k heads consecutively
            BigDecimal pOther = P(N-k-1, 0, q-1).subtract(P(N-k-1, k, q-1));
            Preconditions.checkArgument(pOther.compareTo(BigDecimal.ZERO) >= 0);
            ret = ret.add(pOther.multiply(TAILS).multiply(HEADS.pow(k)));
        }

        PCACHE.put(args, ret);
        return ret;
    }

    private static BigDecimal exact(int N, int k, int q) {
        BigDecimal exactK1 = P(N, k, q).subtract(P(N, k+1, q));
        if (q > 0) {
            BigDecimal exactK2 = P(N, k, q-1).subtract(P(N, k+1, q-1));
            return exactK1.subtract(exactK2);
        } else {
            return exactK1;
        }
    }

    @AutoValue
    abstract static class MArgs {
        public static MArgs make(int rows, int atMost) {
            return new AutoValue_Brilliant_MArgs(rows, atMost);
        }
        public abstract int rows();
        public abstract int atMost();
    }

    private static BigDecimal atMost(BigDecimal[] numInconv, Map<MArgs, BigDecimal> cache, int rows, int atMost) {
        MArgs args = MArgs.make(rows, atMost);
        if (cache.containsKey(args)) return cache.get(args);

        int C = numInconv.length - 1;
        BigDecimal ret;
        if (rows == 0) {
            ret = BigDecimal.ONE;
        } else {
            ret = BigDecimal.ZERO;
            for (int x = 0; x <= Math.min(C, atMost); x++) {
                ret = ret.add(numInconv[x].multiply(atMost(numInconv, cache, rows-1, atMost-x)));
            }
        }

        cache.put(args, ret);
        return ret;
    }

    // private static final int N = 1_000_000;
    public static void main(String[] args) throws NumberFormatException, IOException {
        int c = 1;
        while (true) {
            BigDecimal[] pInconv = new BigDecimal[c+1];
            for (int i = 0; i < c+1; i++) pInconv[i] = BigDecimal.ZERO;

            for (int k = 0; k <= c; k++) for (int q = 0; q <= c - k; q++) {
                BigDecimal p = exact(c, k, q);

                int numInconv = c - k - q;
                pInconv[numInconv] = pInconv[numInconv].add(p);
            }
            System.out.println(c + ": " + (1 - atMost(pInconv, Maps.newHashMap(), 25, (25*c)/10).doubleValue()));

            try { Thread.sleep(400); } catch (InterruptedException ignore) {}
            c++;
        }
    }

}