Project Euler 743 - Window into a matrix

Official link: https://projecteuler.net/problem=743

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

Thought Process

Now we need to build 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. Notice the following:

Using this recursive pattern the problem becomes much more efficient.

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