UVA10518 - How Many Calls?（矩陣快速冪）

UVA10518 - How Many Calls?（矩陣快速冪）

UVA10518 - How Many Calls?（矩陣快速冪）

題目鏈接

題目大意:給你fibonacci數列怎麼求的，然後問你求f（n) = f（n - 1) + f(n - 2)需要多少次調用，並且這個數很大，取模一個進制的數。

解題思路：要發現F(n) = 2 *f(n) - 1這個規律，估計要很熟系fibonacci數列，我明明推出了好多項後但是一點也沒有發現規律。然後要用矩陣快速冪來求fibonacci，因為n很大。構造這樣的矩陣
1， 1 （2*2矩陣） * f（n - 1） (2*1矩陣) 等於 f（n - 1) + f(n - 2)(2*1矩陣)
1， 0 f (n - 2) f(n - 1)


這樣就可以用前面的那麼系數矩陣的n次冪乘上f（1） 這個矩陣得到最後想要的答案。
f（0）

代碼：

#include 
#include 

typedef long long ll;
const int maxn = 2;
int base;

struct Mat {

    int s[maxn][maxn];

    void init () {
        s[0][0] = s[0][1] = s[1][0] = 1;
        s[1][1] = 0;
    }

    Mat operator ^ (const Mat& t) const {

        Mat arr;    
        memset (arr.s, 0, sizeof(arr.s));

        for (int i = 0; i < maxn; i++)
            for (int j = 0; j < maxn; j++)
                for (int k = 0; k < maxn; k++) 
                    arr.s[i][j] = (arr.s[i][j] + s[i][k] * t.s[k][j]) % base;
        return arr; 
    }
};

Mat Fmod (ll n, Mat a) {

    if (n == 1)
        return a; 

    Mat tmp = Fmod(n/2, a);
    tmp = tmp ^ tmp;
    if (n % 2 == 1)
        tmp = tmp ^ a;

/*    printf ("%lld\n", n);
    for (int i = 0; i < maxn; i++)
            printf ("%d %d\n", tmp.s[i][0], tmp.s[i][1]);*/
    return tmp;
}

int main () {

    ll n;
    int cas = 0;
    Mat a, ans;

    while (scanf ("%lld%d", &n, &base) && (n || base)) {

        a.init();
        if (n)
            ans = Fmod(n, a);    
        else
            ans = a;
        printf ("Case %d: %lld %d %d\n", ++cas, n, base, (ans.s[0][0] * 2 + base - 1) % base);
    }
    return 0;
}