Recursive sequence（HDU5950 矩陣快速冪）

題目：HDU5954

題意：

奶牛報數，先給兩個數a和b，分別是f[n-2],f[n-1]，之後每頭奶牛i報數為f[i-1] + 2 * f[i-2] + i^4;給出n，求din頭奶牛要報的數字，對2147493647取餘。

思路：

看到這個式子知道這是一個矩陣快速冪，然後開始推式子，在我給隊友寫出平方差公式來隊友看到楊輝三角形式後後，就去推7*7的矩陣快速冪了，但因為剛剛學這個，但結束就掛死在這個題上了。

式子：

 之後就是套裸的矩陣快速冪就好了，個人感覺做題補題真的是長知識最快的方法啊。補題的時候自己直接用矩陣來寫麻煩的要死，就把矩陣放在一個結構體中，順便方便很多。

代碼：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;
const ll MOD = 2147493647;
struct Maxt {
    ll mp[8][8];
    Maxt() {
        for(int i = 1; i<=7; i++) {
            for(int j = 1; j<=7; j++) {
                mp[i][j] = 0;
            }
        }
    }
} fp,tmp;
int n,a,b,T;
int read() {
    int res = 0;
    char op;
    op = getchar();
    if(op>='0' && op<='9') {
        res = op-'0';
        op = getchar();
    }
    while(op>='0' && op<='9') {
        res = res*10 + op-'0';
        op = getchar();
    }
    return res;
}

void init() {
    for(int i = 1; i<=7; i++) {
        for(int j =1; j<=7; j++) {
            fp.mp[i][j] = 0;
            tmp.mp[i][j] = 0;
        }
    }
    fp.mp[1][1] = 1,fp.mp[2][1] = 1,fp.mp[2][2] = 1,fp.mp[7][6] = 1;
    fp.mp[3][1] = 1,fp.mp[3][2] = 2,fp.mp[3][3] = 1,fp.mp[4][1] = 1;
    fp.mp[4][2] = 3,fp.mp[4][3] = 3,fp.mp[4][4] = 1,fp.mp[5][1] = 1;
    fp.mp[5][2] = 4,fp.mp[5][3] = 6,fp.mp[5][4] = 4,fp.mp[5][5] = 1;
    fp.mp[6][5] = 1,fp.mp[6][6] = 1,fp.mp[6][7] = 2;
    tmp.mp[1][1] = 1,tmp.mp[2][1] = 3,tmp.mp[3][1] = 9,tmp.mp[4][1] = 27,tmp.mp[5][1] = 81,tmp.mp[6][1] = b,tmp.mp[7][1] = a;
}

Maxt Maxtcalc(const Maxt& a,const Maxt& b) {
    Maxt t;
    for(int i = 1; i<=7; i++) {
        for(int j = 1; j<=7; j++) {
            t.mp[i][j] = 0;
            for(int k = 1; k<=7; k++) {
                t.mp[i][j] = (t.mp[i][j] + (a.mp[i][k]*b.mp[k][j]) % MOD) % MOD;
            }
        }
    }
    return t;
}

Maxt qcalc(int x,Maxt s) {
    Maxt tmp;
    for(int i = 1; i<=7; i++) {
        tmp.mp[i][i] = 1;
    }
    while(x) {
        if(x&1) {
            tmp = Maxtcalc(tmp, s);
        }
        s = Maxtcalc(s, s);
        x>>=1;
    }
    return tmp;
}

int main() {
    T = read();
    while(T--) {
        n = read();
        a = read();
        b= read();
        if(n == 1) {
            printf("%d\n",a);
            continue;
        }
        if(n == 2) {
            printf("%d\n",b);
            continue;
        }
        if(n == 3) {
            printf("%d\n",81+2*a+b);
            continue;
        }
        n = n-2;
        init();
        fp = qcalc(n,fp);
        Maxt ans =  Maxtcalc(fp, tmp);
        printf("%lld\n",ans.mp[6][1]%MOD);
    }
    return 0;
}
/*
樣例輸入：
2
3 1 2
4 1 10
樣例輸出：
85
369
*/