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
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!
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