对于给定的 n，如何找到具有以下递推关系的序列中的第 n 项？

Question

对于给定的 n，如何在具有以下递归关系的序列中找到第 n 项？

F(n) = 2 * b * F(n – 1) – F(n – 2), F( 0) = a, F(1) = b

其中 a 和 b 是常量。

N的值比较大（1≤n≤10¹²）因此需要矩阵求幂。

这是我的代码； ll 是 long long int 的类型定义，值取模 r.

void multiply(ll F[2][2], ll M[2][2])
{
    ll x = ((F[0][0] * M[0][0]) % r + (F[0][1] * M[1][0]) % r) % r;
    ll y = ((F[0][0] * M[0][1]) % r + (F[0][1] * M[1][1]) % r) % r;
    ll z = ((F[1][0] * M[0][0]) % r + (F[1][1] * M[1][0]) % r) % r;
    ll w = ((F[1][0] * M[0][1]) % r + (F[1][1] * M[1][1]) % r) % r;
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}
void power(ll F[2][2], ll n, ll b)
{
    if (n == 0 || n == 1)
        return;
    ll M[2][2] = {{2 * b, -1}, {1, 0}};
    power(F, n / 2,b);
    multiply(F, F);
    if (n % 2 != 0)
        multiply(F, M);
}
ll rec(ll n, ll b, ll a)
{
    ll F[2][2] = {{2 * b, -1}, {1, 0}};
    if (n == 0)
        return a;
    if (n == 1)
        return b;
    power(F, n - 1,b);
    return F[0][0] % r;
}

然而，我在所有情况下都面临获取所需值的问题，即我在某些情况下得到 错误答案 (WA) 判决。

谁能帮我解决这个问题并指出这段代码中的错误，这样我以后就可以自己解决这类问题了？

P.S. 这里是第一个计时器。如果我做错了什么而错过了任何东西，我深表歉意。

Answer 1

WA 的可能原因是，您 return a 或 b 没有做任何 mod。试试吧。

if (n == 0)
    return a%r;
if (n == 1)
    return b%r;

如果你还在搞WA，请给出一些测试用例或者问题link。

Answer 2

技术：或许您被要求找到值 res 模 r 以便 0 <= res < r。但是，通过在矩阵中使用-1，实际上可以得到负的中间值和最终值。原因是，在大多数编程语言中，模运算实际上使用向零四舍五入的除法，因此产生的结果范围为 -r < res < r (example link ).

尝试以下任一方法：

将 -1 更改为 r - 1，以便所有中间值保持非负数。
通过返回 (F[0][0] + r) % r 而不是仅返回 F[0][0] % r 来修复最终结果。

公式：你的公式看起来不对。从逻辑上讲，你的 rec 函数说除了 F(0) 之外没有任何东西依赖于 a，这显然是错误的。

回想一下我们为什么以及如何首先使用矩阵：

( F(n)   )  =  ( 2b   -1 )   *  ( F(n-1) )
( F(n-1) )     (  1    0 )      ( F(n-2) )

在这里，我们通过将 2x2 矩阵和 2x1 向量相乘得到一个 2x1 向量。然后我们查看它的顶部元素，并根据乘法规则得到

F(n) = 2b * F(n-1) + (-1) * F(n-2)

重点是，我们可以取矩阵的幂得到如下：

( F(n)   )  =  ( 2b   -1 ) ^{n-1}   *  ( F(1) )
( F(n-1) )     (  1    0 )             ( F(0) )

同理，我们有

F(n) = X * F(1) + Y * F(0)

其中 X 和 Y 是矩阵的第一行：

( 2b   -1 ) ^{n-1}  =  ( X   Y )
(  1    0 )            ( Z   T )

所以 F[0][0] % r 不是答案，真的。真正的答案看起来像

(F[0][0] * b + F[0][1] * a) % r

如果我们可以有负的中间值（见上面的第1点），结果仍然是从-r到r而不是从 0 到 r。要修复它，我们可以再添加一个 r 并再次取模：

((F[0][0] * b + F[0][1] * a) % r + r) % r

对于给定的 n，如何找到具有以下递推关系的序列中的第 n 项？

How to find the n-th term in a sequence with following recurrence relation for a given n?

algorithm

math

matrix

matrix-multiplication

recurrence