Can someone explain this solution to USACO 2013 Gold December Contest: The Bessie Shuffle?

Правка en2, от vamaddur, 2017-07-07 14:25:17

Click Here for Problem

Chinese Solution, since USACO does not have an official solution for the problem above.

I had a lot of trouble with the implementation of this question, so I looked up this solution online. Google Translate could only do so much for the page (the only solution I could find), but I think I was able to discern the following from the code:

1) The array "per" reverses the permutation process, and length of 31 represents a bitmask of that length. 2) The idea behind the "per" is that the result of a number of consecutive permutations can be assembled in logarithmic time. 3) The variable "num" in the third main loop functions as a mask.

However, I do not fully understand the purpose of "bot", "now", and "k" in the third main loop, and the mathematics in the first and third main loops.

I would appreciate an explanation for these parts of the solution.

Thanks in advance!

Теги usaco, adhoc

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский vamaddur 2017-07-25 09:45:36 8
en3 Английский vamaddur 2017-07-07 14:25:38 4
en2 Английский vamaddur 2017-07-07 14:25:17 2 Tiny change: 'pid=366)\n[Chinese' -> 'pid=366)\n\n[Chinese'
en1 Английский vamaddur 2017-07-07 14:24:48 1142 Initial revision (published)