Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author: maxcruickshanks
Subtask 1
Initialize an array
with the values from
and
, where
is the position of
after applying the operation once (i.e.,
).
Next, for each of the
rounds, set
to
for every index
(
).
Finally, output
.
Time Complexity: 
Subtask 2
Redefine
as the position of
after applying the operation
times.
Build
for
and
(since
) by knowing that
.
If the
bit is toggled in the binary representation of
, set
to
.
Finally, output
.
Time Complexity: 
Alternative Solution
Note that binary lifting is not the only solution to this problem.
Observe that
will repeat after at most
rounds since the maximum cycle length is
.
It suffices to determine the cycles and shift each by
modulo the length of the cycle.
The implementation details are left as an exercise to the reader.
Time Complexity: 
Comments