Editorial for COCI '09 Contest 1 #5 Genijalac
Submitting an official solution before solving the problem yourself is a bannable offence.
We construct a directed graph with vertices, labeled by numbers
to
. All edges will be of the form
for each
smaller than or equal to
where
is the shuffle sequence given in the input. It is clear that each vertex has exactly one incoming and one outgoing edge, because for each
and
,
is
. Such a graph contains one or more components, where each component is a cycle of length
. Note that this graph uniquely represents the output sequence of Mirko's machine.
We now compute cycle lengths for each component. We construct an array that stores the length of the cycle containing vertex
. This can be constructed in
time. We can now determine for any columns
to
the number of rows between two repetitions of the original ordering as
where
is the least common multiple function. We now know that the rows we are interested in are given as
where
is a nonnegative integer. The solution to the original problem is now the number of nonnegative integers
that satisfy:
This can be easily solved.
Comments