矩阵快速幂 之 快速求递推序列的第N项

1242 斐波那契数列的第N项 

基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题

斐波那契数列的定义如下：

F(0) = 0

F(1) = 1

F(n) = F(n - 1) + F(n - 2) (n >= 2)

(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...)

给出n，求F(n)，由于结果很大，输出F(n) % 1000000009的结果即可。

Input

输入1个数n(1 <= n <= 10^18)。

Output

输出F(n) % 1000000009的结果。

Input示例

11

Output示例

89

//快速幂矩阵求fib数列  
F(0) = 0  
F(1) = 1  
F(2) = 1  
F(3) = 2  
#include <iostream>  
#include <algorithm>  
#include <cstring>  
#define ll long long  
#define MOD 1000000009  
#define endl "\n"  
using namespace std;  
void matrix_mul(ll a[][2], ll b[][2]){  
    ll c[2][2];  
    c[0][0] = a[0][0]*b[0][0] + a[0][1]*b[1][0];  
    c[0][1] = a[0][0]*b[0][1] + a[0][1]*b[1][1];  
    c[1][0] = a[1][0]*b[0][0] + a[1][1]*b[1][0];  
    c[1][1] = a[1][0]*b[0][1] + a[1][1]*b[1][1];  
    for (int i = 0; i < 2; ++i) {  
        for (int j = 0; j < 2; ++j) {  
            a[i][j] = c[i][j] % MOD;  
        }  
    }  
}  
  
int main (){  
    int n;  
    ll a[2][2];  
    ll ans[2][2];  
    while (cin>>n){  
        a[0][0] = a[0][1] = a[1][0] = 1;  
        a[1][1] = 0;  
        ans[0][0] = ans[1][1] = 1;  
        ans[0][1] = ans[1][0] = 0;  
        while(n){  
            if(n&1)  
                matrix_mul(ans, a);  
            matrix_mul(a, a);  
            n>>=1;  
        }  
        cout<<ans[1][0]<<endl;  
    }  
    return 0;  
}  

变式应用

1126 求递推序列的第N项

有一个序列是这样定义的：f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

给出A，B和N，求f(n)的值。

Input

输入3个数：A,B,N。数字之间用空格分割。(-10000 <= A, B <= 10000, 1 <= N <= 10^9)

Output

输出f(n)的值。

首先找规律，一般来说对MOD = 7这种小数来说，余数结果只有0,1,2,3,4,5,6。是我们可以在能接受时间内找出循环节的。利用鸽巢原理(桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理有时也被称为鸽巢原理。是组合数学中一个重要的原理) 每个f(n)有7种可能，而f(n)由组合[f(n-1)，f(n-2)]递推出来。所以说一共只有7*7=49种可能性，也就是说周期最大为49.

对于这题只要找出循环节就能得到answer了。

for (i = 3; i < 300; i++)
{
    f[i] = ((A * f[i - 1] + B * f[i - 2]) % 7 + 7) % 7;
    cout<<f[i]<<" ";
//            if (f[i - 1] == 1 && f[i] == 1)
//            {
//                break;
//            }
}

另外我们也可以利用上面学习的快速幂来求解。对应相乘系数改成A、B即可

#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
#define MOD 7
#define endl "\n"
using namespace std;
void matrix_mul(ll a[][2], ll b[][2]){
    ll c[2][2];
    c[0][0] = a[0][0]*b[0][0] + a[0][1]*b[1][0];
    c[0][1] = a[0][0]*b[0][1] + a[0][1]*b[1][1];
    c[1][0] = a[1][0]*b[0][0] + a[1][1]*b[1][0];
    c[1][1] = a[1][0]*b[0][1] + a[1][1]*b[1][1];
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            a[i][j] = c[i][j]% MOD;
        }
    }
}

int main (){
    int n;
    ll a[2][2];
    ll ans[2][2];
    int A, B;
    while (cin>>A>>B>>n){
        if (n==1 || n==2){
            cout<<1<<endl;
            break;
        }
        a[0][0] =(A%MOD +MOD)%MOD, a[0][1] = (B%MOD +MOD)%MOD;  //预处理 去负号 余数
        a[1][0] = 1;
        a[1][1] = 0;
        ans[0][0] = ans[1][1] = 1;
        ans[0][1] = ans[1][0] = 0;
        n-=2;   //1  1  A+B  A^2+B+AB  
        while(n){   //快速幂模板
            if(n&1)
                matrix_mul(ans, a);
            matrix_mul(a, a);
            n>>=1;
        }

        cout<<endl<<(ans[0][0] + ans[0][1])%MOD<<endl;
    }
    return 0;
}

至于为什么要n-=2，就需要各位因题而异，根据模板来自己写出对应的的矩阵递推公式来。

如上就是这题的公式。大家潦草看一下。

也就是A*f(n-1) + B*f(n-2) = f(n). 

我们可以看到其实就是一个等比数列：An = A1 * q^(n-1).

当然大家可以手算一下a3、a4、a5 .... 以及q^2、q^3来验证一下结果，以及感受一下推导过程。

                                        

当n=3时，取q^(n-2),     [0][0] = A、             [0][1] = B                a3=.A+B。

当n=4时，取q^(n-2),     [0][0] = A^2+B、    [0][1] = AB             a4=A^2+B+AB.

    ...    ....    ...