I had no problem scoring 40 points on this problem:

- Calculate each number’s amount of divisors. Pollard Rho is an efficient way to do this but brute prime factorization was enough.
- Notice that finding out the game was a losing state could be obtained by getting the binary representation of each heap, and making sure the independent sum of each bit was divisible by 3.
- Handle lists of frequencies with all possible states, which could be trivially multiplied in O((3^{log(p)})^2), where p is the maximum number of divisors a number could have.
- Having defined this list multiplication, apply binary exponentiation and you have a O((3^{log(p)})^2log(k)) solution.

Where I struggled was on the original constraints (100 points). I figured some kind of transform was needed to multiply faster, but since the exponent operation was weird, it wasn’t as simple as copy-pasting a classic FFT or WHT implementation. It was necessary to dig into the theory.

So I did. After looking this up, I thought a WHT (Walsh-Hadamard Transform) with a matrix of size 3 x 3 could do the trick, the only thing left was to find the transformation matrix. Here is where I started to struggle. I tried to write down and solve the equation

T(a) \cdot T(b) = T(a \$ b)

(where \$ is the list multiplication operand, \cdot is the dot product, T is the transformation matrix, and a and b are the two lists).

But it got very tedious, and the equation wasn’t so friendly. So I created a bruteforce solution that created all possible transformation matrices and tested them on random vectors, and made sure an invertible matrix was found. The possible values on the matrices were \{1,-1\}. So I got nothing. After reading some more, I thought maybe more roots of unity were needed, so I tried with \{1, -1, i, -i\}. Nothing either. So I basically gave up and closed my laptop (it was Saturday night, I needed beer).

This morning I open AC’ed 100 solutions, and saw that I had figured out everything right, I was just missing the transformation matrix. Turns out it’s some weird shit that isn’t even conformed by roots of unity (value (-1 -i) is used!).

So yeah, theory killed me in this problem, I’m not a strong enough mathematician. Attacking this problem left me with a huge amount of questions. If someone could help me understand them I’d really appreciate it!.

Why do non-roots of unity work in this problem? If I find a matrix that fits with the transform operation I’m working on and is invertible, can I use it in WHT with no extra conditions at all?

Additionally, I find it fascinating how WHT works for transformations on several dimensions. In this problem, all dimensions had the same operation (sum modulo 3). Is it possible to have different operations across these dimensions? (assuming each has a valid invertible transformation matrix, of course). Or even further, applying different operations with matrices of different sizes?.

Finally, what is a good approach to understanding the proof of correctness of WHT? It is a major blackbox to me right now and I’d really like to get how it works.

Please help