Sure! Without this one, the code is more complicated than expected.

I guess it's your implementation's problem. I faced the same but changed something in data structure and now it works. I'm sure it's because function composition and matrix multiplication are non-commutative so the order of evalutation should be preserved.

I didn't have problems with min though.

For every fixed k, c[j] is exactly the number of partitions of j using only numbers from 1 to k after inner cycle. This is possible to prove by induction.

a) When k=1, c[j]=1 for all j from 0 to n because the only way to make a partition of any integer with only 1's is simply 1+1+...+1.

b) Now suppose it's true for k-1 and for all j < j' for k. To get partitions of j with term k, we need to append k to all partitions of j-k. Since c[j-k] has correct value by induction hypothesis, we get correct value for c[j] by adding c[j-k].

Then calculations up to k=n give c[n] as answer.

UPD: while writing this, I noticed the comments in the code are about generating function of number of integer partitions. Then I recommend to check https://en.wikipedia.org/wiki/Partition_(number_theory) (part about generating function) and https://en.wikipedia.org/wiki/Generating_function. The algorithm is easy to interpret in terms of operations with generating functions.

Glad to see the Gaussian elimination here!

I guess using Riemann zeta function was a kind of overkill :)

Great kata! I had to remember some interesting sqrt-algorithms to deal with this!

This is modification of digit-by-digit calculation method

Можно оптимизировать, создав "result" сразу размера "numbers.size()", чтобы не выполнялись лишние медленные перевыделения памяти.
(It can be optimized by creating "result" with exact size "numbers.size()" - this prevents slow memory reallocations.)

What if dna.size() > 100?

Yeah, you're right (I don't care it was 3 years ago :) )

Holy cow, that's a massive one!