algorithm - 解决复发

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 个元素分成 2 组，其中最大的元素进入第 1 组，第 2 大的进入第 2 组，第 3 大的进入第 1 组等等......最后需要找到总和的绝对差两个集合的元素。

我可以在不计算所有元素的情况下找到这种差异，因为 N 可以大到 10^7 和 A,B,C,X 最大为 100。

Answer 1

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

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