You could potentially use a run (or runs) through the O(n^100) problem to optimize approaches for smaller problems. If you were lucky that would ammortize the cost of the first run.

With a bit of luck you might also be able to come up with a scheme to generate optimal nonuniform circuits for smaller problem sizes, which would ammortize nicely if you had enough of the smaller instances to solve.