Project Euler 154 - Exploring Pascal's pyramid

A triangular pyramid is constructed using spherical balls so that each ball rests on exactly three balls of the next lower level.

Then, we calculate the number of paths leading from the apex to each position:
A path starts at the apex and progresses downwards to any of the three spheres directly below the current position.
Consequently, the number of paths to reach a certain position is the sum of the numbers immediately above it (depending on the position, there are up to three numbers above it).
The result is Pascal's pyramid and the numbers at each level n are the coefficients of the trinomial expansion (x + y + z)ⁿ.
How many coefficients in the expansion of (x + y + z)²⁰⁰⁰⁰⁰ are multiples of 10¹²?

Solution

I have spent a week to solve this problem.

First step is observe the pattern

Now we can see the for any given level l, any row m (starting 0), any column n (starting 0), the value is C_l^m * C_mⁿ

Due to the symmetry, there is no need to go through the entire a triangle. Only going through the red ones is sufficient.


To illustrate the idea, considering peeling an onion, we take off the outermost layer of the triangle, what is left is:


Then again take off the outermost layer, what is left is:


The complexity of the algorithm is O(n^2), which runs 19 minutes on my iMac. I struggle to make it run any faster.