如何求解大规模n下递推序列第n项？矩阵快速幂遇WA问题

你遇到的这个WA问题很常见，我帮你梳理几个最容易踩的坑，结合你的递推式和场景逐一分析：

1. 转移矩阵构造是否正确 #

首先要确认你的矩阵快速幂用的转移矩阵是否匹配递推式 F(n) = 2b*F(n-1) - F(n-2)。正确的转移矩阵应该是这样的：

[ 2b  -1 ]
[  1   0 ]

对应的初始向量是 [F(1), F(0)] 也就是 [b, a]。计算时，我们是用这个矩阵的 n-1 次幂乘以初始向量，得到的第一个元素就是 F(n)。如果矩阵的行/列搞反了，或者初始向量顺序写反（比如写成 [a, b]），那结果肯定不对，这是很多人第一次写矩阵快速幂容易犯的错。

2. 模运算的负数处理要到位 #

递推式里有减法项 -F(n-2)，计算过程中很容易出现负数结果。而C/C++里的 % 运算符对负数的处理是返回负余数，比如 (-1) % 5 会得到 -1，但我们需要的是 4 这种正余数。所以所有涉及模运算的地方，都要把结果调整到非负范围：

// 正确的取模方式
ll safe_mod(ll x, ll mod) {
    return (x % mod + mod) % mod;
}

不管是矩阵乘法的每个元素，还是最终结果，都要用上这个处理，否则遇到负数的测试用例直接就WA了。

3. 数据溢出的问题不能忽略 #

虽然你用了 long long（ll），但当 r 很大（比如接近1e18）时，两个 ll 相乘会直接溢出 long long 的范围（毕竟 long long 最大也就约9e18）。这时候普通的乘法会得到错误的中间值，导致最终结果错误。解决办法有两种：

• 用快速乘法（模乘法）：把乘法拆解成加法结合二进制运算，避免溢出，实现示例：

  ll mul_mod(ll a, ll b, ll mod) {
      ll res = 0;
      a = safe_mod(a, mod);
      while (b > 0) {
          if (b & 1) {
              res = safe_mod(res + a, mod);
          }
          a = safe_mod(a * 2, mod);
          b >>= 1;
      }
      return res;
  }
  

• 如果你的编译器支持 __int128 类型，可以直接用它来计算乘法再取模，代码更简洁：

  ll mul_mod(ll a, ll b, ll mod) {
      return ( (__int128)a * b ) % mod;
  }
  

矩阵乘法里的每一次乘法运算都要用这个 mul_mod 代替普通乘法，否则溢出后结果必然错误。

4. 边界条件的特殊处理 #

题目里n的范围是 1≤n≤1e12，那n=1的时候直接返回 b % r 就可以了，不需要跑矩阵幂运算。虽然矩阵幂计算n-1=0（单位矩阵）也能得到正确结果，但如果你的代码在处理极小n值时逻辑有问题（比如n=0的情况，虽然题目没要求，但代码里如果没判断可能影响其他情况），也可能导致WA。建议在代码开头先判断：

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

5. 模运算的一致性检查 #

确保矩阵快速幂的每一步运算（矩阵乘法、矩阵幂的迭代过程）都及时取模了。如果某一步忘记取模，中间结果会变得极大，不仅容易溢出，还会导致后续计算全部错误。比如矩阵乘法时，每个元素计算后都要立刻用 safe_mod 处理，而不是等到最后才取模。

6. 小例子验证法 #

你可以手动计算几个小n值的结果，和代码输出对比，快速定位问题：

• n=2: F(2) = 2*b*b - a
• n=3: F(3) = 2*b*(2*b² -a) - b = 4b³ - 2ab -b
  比如代入a=1, b=2, r=100，n=2的结果是 2*2*2 -1=7，n=3是 4*8 -2*1*2 -2=32-4-2=26，看看代码输出是否一致。如果小例子都错了，那肯定是矩阵构造或者计算逻辑的问题。

内容的提问来源于stack exchange，提问作者hajas