Thought Process

This was a bit of a disappointing problem in my opinion. Even with optimized code it feels impossible to reach the 1 minute benchmark in python. Once I solved the problem I could see that my solution was just as good as many other solutions in the thread.

Anyways, back to how I solved it. The first obvious step is to investigate the Wikipedia page Pascal's Pyramid there we get the useful identity that the co-efficient of x^i * y^j * z^k, which we denote with C(i, j, k) = n! / (i! j! k!) is equal to C(i, j) * C(j, k) where C(i, j) denotes the co-efficient of x^i * y^j in the binomial expansion, and we can also notice some symmetries in Pascal's triangle, which greatly speedup our algorithm:

1. Notice that if i = j = k then C(i, j, k) is the unique center of that layer

2. Otherwise if i = j or  j = k  (We don't need to check if i = k since this would imply the above condition) then C(i, j, k) appears 3 times on that level

3. Finally, none are equal to each other, C(i, j, k) appears 6 times on that level

Now this is what I believe is the key step. Once you realise that you only care about 10^12 = 2^12 * 5^12 it is obvious that you only need to keep track of the amount of 2's and 5's which divide any co-efficient. 

Now the algorithm is simple:

1. Pre-calculate how many 2's and 5's divide every n from 1 to 200,000

2. Use the above to pre-calculate how many 2's and 5's divide every n! from 1 to 200,000

   1. Now we can quickly find how many 2's and 5's divide every co-efficient C(i, j, k) = n! / (i! j! k!)

3. By our previous observations, we can split the triangle into thirds and only care about one of them hence we loop through all i, j, k where i < j + 1 < k + 1. That is loop through i = 1 to 200,000//3

   1. Loop through j = i to (200,000 - i)//2

      1. k = 200,000 - i - j

      2. Now test if C(i, j, k) has at least 12 factors of 2's and 5's

         1. If yes, add the corresponding about of entries based on previous observations

It is simple enough to adjust this algorithm for any power N of (x + y + z) and adjust the multiple to be of the form a^ae * b^be which is what Stephan Brumme did, and (without looking at what he did), I used his page to have more test cases which I always find extremely useful while debugging! (I had a few error bounds on i, j for my first attempt)