題目描述：

Winder 最近在學(xué)習(xí) fibonacci 數(shù)列的相關(guān)知識砸抛。我們都知道 fibonacci 數(shù)列的遞推公式是F(n) = F(n - 1) + F(n - 2)（n >= 2 且 n 為整數(shù)）邀跃。

Winder 想知道的是當(dāng)我們將這個遞推式改為F(n) = a * F(n - 1) + b * F(n - 2)（n >= 2 且 n 為整數(shù)）時我們得到的是怎樣的數(shù)列策添。但是，Winder 很懶定躏，所以只能由你來幫他來完成這件事患雇。

注意，這里我們依然令 F（0）=F（1）=1胞得。

輸入格式：

輸入第一行三個正整數(shù) q, a, b。

接下來有 q 行屹电，每行一個自然數(shù) n阶剑。

對于50%的數(shù)據(jù)，1 <= q危号、n <= 1000牧愁。

對于80%的數(shù)據(jù)，1 <= q葱色、n <= 100000递宅。

對于100%的數(shù)據(jù)，1 <= q <= 100000,1 <= n <= 1000000000,1 <= a苍狰、b <= 1000办龄。

輸出格式

輸出一行一個整數(shù) F（n），由于結(jié)果可能會很大淋昭，Winder 要求輸出結(jié)果對 2013 取模俐填，即將 F（n）對2013求余后輸出。

樣例輸入

5 4 5
2
4
8
16
32

樣例輸出

9
209
1377
182
9

方法一：

剛開始拿到題目的時候第一反應(yīng)是按要求做一個遞歸算法翔忽，但是后來發(fā)現(xiàn)遞歸的代價太大英融，可能會過不了。

方法二：

和方法一一個思路歇式，但是使用了非遞歸算法驶悟，雖然肯定不是最優(yōu)算法，但是應(yīng)該可以得一個基礎(chǔ)分了材失。

#include <iostream>
using namespace std;
int fibonacci(int n, int a, int b)
{
       if (n <= 1)
              return 1;
       else
       {
              int current = 0;
              int pre1 = 1;
              int pre2 = 1;
              for (int i = 2; i <= n; i++)
              {
                     current = (a * pre1 + b * pre2) % 2013;
                     pre2 = pre1;
                     pre1 = current;
              }
              return current;
       }
}
int main()
{
       int q, a, b;
       cin >> q >> a >> b;
       int *result = new int[q];
       for (int i = 0; i < q; i++) {
              int n;
              cin >> n;
              result[i] = fibonacci(n, a, b);
       }
       for (int i = 0; i < q; i++) {
              cout << result[i] << endl;
       }
       delete[]result;
       return 0;
}

方法三：

這個是在理解了矩陣快速冪的思想基礎(chǔ)上痕鳍，進行改進的一個算法，把問題規(guī)模直接降了一大截。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
const int MOD = 2013;
 
struct matrix {     //矩陣 
    int m[2][2];
}ans;
 
matrix multi(matrix a, matrix b) {  //矩陣相乘笼呆，返回一個矩陣 
    matrix tmp;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            tmp.m[i][j] = 0;
            for (int k = 0; k < 2; k++)
                tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;
        }
    }
    return tmp;
}
 
matrix matrix_pow(matrix a, int n) {   //矩陣快速冪熊响，矩陣a的n次冪 
    ans.m[0][0] = ans.m[1][1] = 1;  //初始化為單位矩陣 
    ans.m[0][1] = ans.m[1][0] = 0;
    while (n) {
        if (n & 1) ans = multi(ans, a);
        a = multi(a, a);
        n >>= 1;
    }
    return ans;
}
 
int main() {
    int q, n, a, b;
    cin >> q >> a >> b;
    int* result = new int[q];
    matrix mul;
    mul.m[0][0] = a;
    mul.m[0][1] = b;
    mul.m[1][0] = 1;
    mul.m[1][1] = 0;
    for (int i = 0; i < q; i++) {
        int n;
        cin >> n;
        matrix mm = matrix_pow(mul, n - 1);
        result[i] = (mm.m[0][0] + mm.m[0][1])%MOD;
    }
    for (int i = 0; i < q; i++) {
        cout << result[i] << endl;
    }
    delete[]result;
    return 0;
}

第一次做的時候因為最后一步的時候在result[i] = (mm.m[0][0] + mm.m[0][1])%MOD的時候忘記了加這個“%MOD”，導(dǎo)致結(jié)果一直有部分不對诗赌，調(diào)試了將近一個上午汗茄。