HDU

题意：f[1]=a,f[2]=b,f[i]=f[i-1]+2*f[i-2]+i^4(I>=3),求f[n]%mod

明显的矩阵快速幂。

这是我一开始的矩阵

 这是结果的

还是太年轻了

struct Mat {
    ll m[7][7];
};

Mat E;

Mat P;

void init() {
    for (int i = 0; i < 7; i++) E.m[i][i] = 1;
    for (int i = 0; i < 6; i++) P.m[i][i] = 1;
    P.m[1][0] = 1;
    P.m[2][0] = 1;
    P.m[2][1] = 2;
    P.m[2][0] = 1;
    P.m[3][0] = 1;
    P.m[3][1] = P.m[3][2] = 3;
    P.m[4][0] = P.m[5][4] = 1;
    P.m[4][1] = P.m[4][3] = 4;
    P.m[4][2] = 6;
    P.m[5][6] = 2;
    P.m[6][5] = 1;
}

Mat mul(const Mat& a, const Mat& b) {
    Mat c;
    for (int i = 0; i < 7; i++) {
        for (int j = 0; j < 7; j++) {
            c.m[i][j] = 0;
            for (int k = 0; k < 7; k++) c.m[i][j] = (c.m[i][j] + (a.m[i][k] * b.m[k][j]) % MOD) % MOD;
        }
    }
    return c;
}

Mat quickPower(Mat a, ll b) {
    Mat ans = E;
    Mat base = a;
    while (b) {
        if (b & 1ll) ans = mul(ans, base);
        base = mul(base, base);
        b >>= 1;
    }
    return ans;
}

int main() {
    init();
    ll n;
    ll a1, a2;
    int T;  
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld%lld",&n , &a1, &a2);
        if (n == 1) {
            printf("%lld
", a1);  continue;
        }
        else if (n == 2) {
            printf("%lld
", a2); continue;
        }
        Mat res = quickPower(P, n - 2);
        ll ans = ((res.m[5][0]*1 + res.m[5][1]*3 + (res.m[5][2]*9)%MOD + (res.m[5][3]*27)%MOD)%MOD + (res.m[5][4] * 81 )%MOD + (res.m[5][5] * (a2))%MOD + (res.m[5][6]* a1)%MOD)%MOD;
        printf("%lld
", ans);
        /*
        for (int i = 0; i < 7; i++) {
            for (int j = 0; j < 7; j++) {
                printf("%lld " ,res.m[i][j]);
            }
            puts("");
        }*/
    }
}