1.
通过逐项计算这个递推式,可以在O(n)的时间内算出答案。对于 n 的规模过大的话效率太低。通过求出通项也不行。斐波那契数列的通项为:
而用矩阵可以高效地求出第 n 项的值。
把斐波那契数列的递推式表示成矩阵就得到了下面的式子
记这个矩阵为 A,则有
因此只要求出 An 就可以求出 Fn 了。复杂度O(log n)
//用二维vector来表示矩阵 typedef vector<int> vec; typedef vector<vec> mat; typedef long long ll; const int M = 10000; // 计算 A * B mat mul(mat &A, mat &B) { mat C(A.szie(), vec(B[0].size())); for (int i = 0; i < A.size(); i++) for (int k = 0; k < B.size(); k++) for (int j = 0; j < B[0].size(); j++) C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % M; return C; } // 计算 A ^ n mat pow(mat A, ll n) { mat B(A.size(), vec(A.size())); for (int i = 0; i < A.size(); i++) B[i][j] = 1; while (n > 0) { if (n & 1) B = mul(B, A); A = mul(A, A); n >>= 1; } return B; } ll n; void solve() { mat A(2, vec(2)); A[0][0] = 1; A[0][1] = 1; A[1][0] = 1; A[1][1] = 0; A = pow(A, n); printf("%d\n", A[1][0]); }
更一般地,对于 m 项递推式,如果记递推式为
则可以把递推式写成如下矩阵形式
通过计算这个矩阵的 n 次幂,就可以在 O(m3 log n)的时间内计算出第 n 项的值。如果递推式里含有常数项则稍微复杂一些,需要变成如下形式
事实上,要求 m 项递推式的第 n 项的值,可以不使用矩阵,而是使用初项的线性表示,通过快速幂在(m2 log n)的时间内求出答案。
//没有找到资料, 如果有会补充