algorithm - SPOJ :Card Shuffling

Question

最近开始解决在线评委的问题。我被困在 this question in SPOJ :

Here is an algorithm for shuffling N cards:

1. The cards are divided into K equal piles, where K is a factor of N.
2. The bottom N / K cards belong to pile 1 in the same order (so the bottom card of the .initial pile is the bottom card of pile 1).
3. The next N / K cards from the bottom belong to pile 2, and so on.
4. Now the top card of the shuffled pile is the top card of pile 1. The next card is the top card of pile 2,..., the Kth card of the shuffled pile is the top card of pile K. Then (K + 1)th card is the card which is now at the top of pile 1, the (K + 2)nd is the card which is now at the top of pile 2 and so on.

For example, if N = 6 and K = 3, the order of a deck of cards "ABCDEF" (top to bottom) when shuffled once would change to "ECAFDB".

Given N and K, what is the least number of shuffles needed after which the pile is restored to its original order?

---

我试过模拟，但它超过了时间限制。有什么数学方程式吗？

Answer 1

是的，这个问题有一个数学解决方案。

首先让我从一些关于如何处理此类问题的技巧开始，然后我将给出一些关于实际解决方案的技巧。我不会完全完成它，所以还有一些挑战。

那么:如何处理此类问题？你所做的实际上是一个好的开始。编写一个模拟并针对一些小案例运行它。那里的模拟应该相当快。现在你有更多的值(value)。把它们写在一张纸上，然后开始盯着它们看。如果 K = x₁ 和 N = y₁ 那么结果是 z₁ 和更多这样的对。试着想出一些公式。关注 x、y 或 z 具有固定值的三元组。他们有什么共同点？等等。你盯着看，通常一段时间后你会想到一个好主意:)

现在:关于这个特定问题的一些提示。进行一次洗牌并记下每张牌的去向。例如，卡片 1 进入位置 3，卡片 3 进入位置 2，依此类推。请注意，某些链将以这种方式形成 - 例如在示例 n=6，k=3 中，我们有一个长度为 6 的链:1->3->2->6->4->5->1 .现在计算所有链的长度(每张卡片都属于一个链)并尝试找出答案如何取决于这些长度。

希望这足以帮助您解决问题。

编辑:查看约束，即使是单次迭代也可能非常缓慢。如果是这样的话，在你完成我在第二个技巧中的建议后，尝试计算链的长度，而不必实际模拟一次洗牌