So, let me get this straight. Yes means yes.

Ja Ja Ja

I don't understand, can you explain?

Of course not, but I got burned by not reading 1D last rated round, so I will look at all of the problems this time

Actually I used to paste the template after the contest started but I figure I can save about a minute if I paste beforehand.

Yeah, but how do you find modulo for which there's an N - th root of unity?

Actually, no, you CAN'T use a modulus for this solution to work.

For a technically correct solution over the reals (or complex numbers), you actually need to check that the sum is 0 for the phi(N) roots of unity w^k for k coprime to n. The vector space V of unreachable vectors has dimension phi(n), so of course you can't check for containment using a single dot product.

But (I guess?) cleverly checking it only for w^1 works because the actual problem's input is so constrained. It's quite likely that [0-9]^N doesn't intersect with the thinner vector space V \ {w^1*i} at all, so there probably aren't any counterexamples or challenge cases to fail on.

This is NOT the case if you move to a nice convenient finite field... then it'd be fairly easy to search for counterexamples that still lie in the space [0-9]^N. For example, using N=30, 3 and 3^7 == 17 are both Nth roots of unity modulo 31. This case will then fail if you're using w=3: "490000000000000000000000000000". 4 + 9*3 == 0 mod 31, but 4 + 9*17 != 0 mod 31, so this is not a reachable vector.

I think if you want to avoid using epsilons to solve this problem, your only choice is to do a proper FFT over a finite field. You can't fake it with a single dot product.

EDIT: Ok, I suppose you'll almost certainly get away with it if you randomize which prime you use. But I think the simplest way to solve this in the actual contest is just to do the dot product for several different roots of unity, so you can pick a weak epsilon (1e-6) and not worry too much.

The intuition is that when you have equidistant points on a circle, you can probably use the roots of unity. Then, as it's customary for problems where you have some transformations and ask yourself if you can reach some state, you should probably search for some invariant.

It's not hard to come up with it, because each operation is basically changing the value of some points which are the n / k-th roots of unity, where k divides n. And it's very well known that:

So this is why it's natural to choose the invariant described above. This way we proved that the condition from above is necessary to reach a value of 0 for all points.

To prove that it's enough, the only way that comes up to my mind is the one from the editorial. Basically you need to check whether $n$-th cyclotomic polynomial Φ_n(x) divides your polynomial, but this is equivalent to checking whether the n-th primitive root of unity is a root of your polynomial, because Φ_n(x) is the minimal polynomial in of the n - th primitive root of unity.