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).