解决递归问题

Question

给定 F(0)=X 和 F(i)=(A⋅F(i−1)^2 + B⋅F(i−1) + C)%1000000，其中 1≤i≤N。

现在给定 N，A，B，C 和 X，如何有效地找到所有的 N 个元素？

我需要将这些 N 个元素分为两组，其中最大的元素放在第一组，第二大的元素放在第二组，第三大的元素放在第一组，以此类推……最后需要找到两组元素的绝对差。

是否可以在不计算所有元素的情况下找到这个差异，因为 N 可以达到 10^7，而 A，B，C，X 最多只能达到 100。

- user132263

---

那有什么使用情况？（原始问题可能是什么） - Alma Do

@AlmaDo 你可以说这是一个棘手的任务..:p - user132263

@user132263，这看起来像是一个递增函数。在i=0处取得最小值，在i=N处达到峰值。你能确认一下吗？ - hemanth

@hemanth 我对此表示怀疑。您如何能说这不取决于A、B、C或X的值呢？ - user132263

@user132263 A、B、C、X 可以取的最小值是多少？ - hemanth

Answer 1

请注意，序列的下一个元素仅取决于前一个元素，并且由于每个结果都是模1000000取整的整数，因此不会有超过M=1000000个不同的元素。因此，从某个点开始，序列是周期性的。您可以生成前几个元素（不超过M），直到找到周期，然后立即知道如果总元素数为N，则每个元素有多少个。

现在，与10^7相比，10^6至少有所改善。一旦您知道从0到999999每个数字在序列中出现的次数，您也可以在O（M）操作中找到所需的差异。

- Gassa

---

嘿，你能否用一些伪代码之类的东西再解释一下吗？我有点听不懂你的意思。 - user132263

有什么不清楚的吗？主要的一点是，如果F(x) = F(y)，那么F(x+1) = F(y+1)，F(x+2) = F(y+2)等等。此外，每个F(x)都是介于0和999999之间的整数，因此最迟在1000000步之后，我们将找到一些F(i) = F(j)。 - Gassa

如何在O（M）操作中查找所需的差异？ - user132263

假设有15个数字999999，没有999998，14个数字999997，15个数字999996，14个数字999995等等。其中，14个999999与零差形成七对。第一个非零差对是999999-999997=2。接下来是12个999997，分为六个零对。下一个非零对是999997-999996。接下来是14个999996，分为七个零对，然后是14个99995，分为七个零对，以此类推。 - Gassa

你需要O(M)的内存来存储0、1、...、M-1出现次数的数量。我们还可以为每个这样的数字K存储第一个x，使得F(x)=K。之后，当某个整数B第二次出现时（它的出现次数变为2），我们已经知道它是哪个整数（B），以及它第一次出现的时间（比如在时间y：F(y)=B）。因此，我们可以计算出周期的长度。我们已经知道周期的元素：它们是第一次出现时间>=y的整数。 - Gassa

Answer 2

如果我是你，我不会害怕计算那些10^7个元素。由于它们的范围在[0 1000000[之间，可以计算值的直方图（1000000个计数器），然后进行后处理以获取所需信息（并遵循@Gassa）。

在迭代公式时要注意溢出，因为F^2无法适应32位。

- user1196549