FFT - Editorial

PROBLEM LINK: Problem

Author and editorialist: Ildar Gainullin

Tester: Hasan Jaddouh

DIFFICULTY: Medium

PREREQUISITES: Combinatorics

EXPLANATION:

Let cnt_x be the number of x's in the given sequence.

Then, easy to see, that if cnt_L is not divisible by L, answer is zero.

Else, answer for fixed L (number of ways to place cnt_L vertices on cycles of length L) is A(cnt_L, L) \cdot A(cnt_L - L, L) \ldots \cdot A(L, L).

Where A(n, k) = C(n, k) * k! = n! / (n - k)!.

And answer for the task is the multiplication of answers for each L.

You can precalculate factorials and their inverses in O(n) (using the fact that 1 / n! = (1 / (n + 1)!) \cdot (n + 1)), so complexity of this algorithm is O(n).

Author’s code

//