Project Euler 537 - Counting Tuples

Official link:

Note: My code took 702 seconds to run, however I am happy with my solution

Thought Process

My first idea was to find the number of partitions of length less than or equal to k for n and then directly calculate the total number of possible outcomes.

For example to calculate T(3, 3)

However generating partitions is too intensive and this method was too slow. 

My next attempt ended up being what almost everyone did.

I investigate the case T(3, 3) further to find the pattern.

It is clear that we can generate B using A! Our goal is achieved. 

After solving the problem I learnt that this type of array multiplication is called a Convolution.

Now it is clear that we just need to generate an array [T(0, 1), T(1, 1), ..., T(n, 1)] and keep convolving (not sure if this is a word?) then to reach [T(0, k), T(1, k), ..., T(n, k)]

However, convolving this k times will take extremely long, instead we use binary exponentiation to get the answer in only 18 steps instead of 20,000.

Interactive Code

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

Code will output T(n, k) (mod 1004535809)