algorithm - 解决二阶问题递归关系的有效算法是什么？

Question

我想求解一个包含二次项的递归关系。

例如.. T(n)= T(n-1)^2 + T(n-1) + 2 是一个递归关系，我必须打印它的和 mod 100000。

如果不使用简单的暴力破解方法，我该怎么做？

Answer 1

根据 n 的大小(例如，大约 10,000,000)，您可以使用一个简单的 for 循环，它会在短时间内运行(例如大约一秒钟)。

我不知道您是否可以找到通用 T(1) 和/或通用递归的数学公式，但我猜您不能。尽管如此，我还是可以告诉你一个可以帮助你解决问题的数学性质。它叫做congruence .简而言之，语法如下:

a =(15)= b

表示 15 整除 b - a。实际的数学符号是一个三行的=，上面写着数字，但我真的不会打!

现在这里有几个对你有用的定理:

1.

a =(n)= b  \
            > => a =(n)= c
b =(n)= c  /

2.

a =(n)= b  =>  a+c =(n)= b+c

3.

a =(n)= b  =>  a*c =(n)= b*c

4.

a =(n)= b  =>  a^2 =(n)= b^2

它们可以很容易地通过编写 a 和 b 来证明:

a = k1*n+r
b = k2*n+r

并应用转换并确保最终 b - a 仍可被 n 整除。

---

也就是说，你的算法变成如下(假设你想要 T1 到 TN mod M 的总和):

T = 3        /* initial T1 */
TSum = T     /* initial sum */

for i=1 to N
    T = (T^2 % M + T + 2) % M
    TSum = (TSum + T) % M

这里要注意的重要一点是 T 和 TSum 总是以 M 为界，并且最大中间结果来自表达式 T^2(对于非平凡的 M)最多可以占用 (M-1)^2。

因此，在您的实现中，您实际上不需要处理非常大的数字，而只需处理大到足以容纳 (M-1)^2 的数据类型。在 C 语言中，uint64_t 就可以了。请注意，对于 M=100000，(M-1)^2 不适合 32 位整数。

这个算法是 O(N) 顺便说一句，所以除非 N 真的很大或者除非它处于非常频繁的循环中，否则它应该足够快日常所需!

---

编辑

这个问题实际上可以用O(M)而不是O(N)来解决。这是因为所有 T(i) 都在 [0, M-1) 范围内，因此计算高达 T(M+1 )，你肯定会循环回来。由于 T(n) 仅依赖于 T(n-1)，因此获取 T(n-1) 的重复值将导致在与第一次相同的值(value)链中。

因此，让我们展开 T 和 TSum 以更好地观察如何利用它。假设 T 生成值 A、B、...、Z 以及 Z 之后>，它循环回到 K，经过几个循环后，它在 P 结束(因为我们到达了 N):

T    A   B   C   D   E   ... K   ...  Z   K   ... Z   K   ... Z   ... K   ... P
TSum AS  BS  CS  DS  ES  ... KS  ...  ZS  KS2 ... ZS2 KS3 ... ZS3 ... KSt ... PSt

所以你的目标是计算PSt。这个想法是计算到 KS2，取其与 KS 的差值，将其乘以 t 并将其添加到 KS 获取 KSt。然后将剩余的相加得到 PSt。

算法如下:

Sums=[M times 0]    /* initially, no sum is calculated */
Indices=[M times 0] /* Indices[i] = I means Sums[i] corresponds to T(1)+...+T(I) */
T = 3           /* initial T1 */
TSum = T        /* initial sum */
Sums[T] = TSum
Indices[T] = 1

for i=2 to N
    T = (T^2 % M + T + 2) % M
    if Sums[T] != 0         /* a loop is detected */
        break

    TSum = (TSum + T) % M
    Sums[T] = TSum
    Indices[T] = i

if i == N
    return TSum

/* compute how many cycles */
cycle_length = i - Indices[T]
t = (N - Indices[T]) / cycle_length

/* add sum of the cycles immediately */
TSum = (Sums[T] + t * (TSum - Sums[T])) % M

/* add what is left */
for i=Indices[T] + t * cycle_length+1 to N
    T = (T^2 % M + T + 2) % M
    TSum = (TSum + T) % M

注意:指数计算可能存在失一误差。如果您计划使用此算法，请仔细检查以确保它不会遗漏任何 T(i) 或对其求和两次。