Project Euler 743 - Window into a matrix

Official link:

Note: Code runs in ~260 seconds, but I am happy with my understanding

Thought Process

Yeah... take a few min's to read and understand all of that....

If you're ready, onto the next part: building a fast algorithm.

Obviously using the formula and compute each combination factor mod 1,000,000,007 is fine but this may take a long time. Using the last part of that whole chunk we have found a recursive way to calculate both of the binomial terms.

We start at f(0) = 1, then f(1) = f(0) * (k-2a) * (k-2a-1) mod 1,000,000,007, then we can using modulo inverse to find 1/(a+1)^2 (In python this would be pow((a+1)^2, -1, 1,000,000,007), and there we go we can now quickly calculate the next combination terms!

Interactive Code

Enter 2 integers separated by a space (k, n)

Code will output A(k,n) % 1,000,000,007

Note: The version in the emulator is a slower version! proper code is given below