HDU 5950 Recursive sequence（矩阵快速幂）

（ACM）数学----矩阵快速幂

题意

• f[n]=f[n-1]+2*f[n-2]+n^4
• 给出f[1],f[2]，求f[n]

题解

• $$\left[ \begin{matrix} f[n] \\ f[n-1] \\ n^4 \\ n^3 \\ n^2 \\ n^1 \\ n^0 \\ \end{matrix} \right] = \left[ \begin{matrix} 1 & 2 & 1 & 4 & 6 & 4 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 4 & 6 & 4 & 1 \\ 0 & 0 & 0 & 1 & 3 & 3 & 1 \\ 0 & 0 & 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{matrix} \right] * \left[ \begin{matrix} f[n-1] \\ f[n-2] \\ (n-1)^4 \\ (n-1)^3 \\ (n-1)^2 \\ (n-1)^1 \\ (n-1)^0 \\ \end{matrix} \right]$$
• $$\left[ \begin{matrix} f[n] \\ f[n-1] \\ n^4 \\ n^3 \\ n^2 \\ n^1 \\ n^0 \\ \end{matrix} \right] = \left[ \begin{matrix} 1 & 2 & 1 & 4 & 6 & 4 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 4 & 6 & 4 & 1 \\ 0 & 0 & 0 & 1 & 3 & 3 & 1 \\ 0 & 0 & 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{matrix} \right] ^ {(n-2)} * \left[ \begin{matrix} f[2] \\ f[1] \\ (2)^4 \\ (2)^3 \\ (2)^2 \\ (2)^1 \\ (2)^0 \\ \end{matrix} \right]$$

代码

#include<cstdio>
#include<cstring>
typedef long long ll;
const ll mod=2147493647;
struct Mat {
    ll mat[8][8];
    Mat() {memset(mat,0,sizeof(mat));}
    Mat operator * (Mat B) {
        Mat C;
        for(int i=1;i<=7;++i) {
            for(int j=1;j<=7;++j) {
                for(int k=1;k<=7;++k) {
                    C.mat[i][j]=(C.mat[i][j]+mat[i][k]*B.mat[k][j]%mod)%mod;
                }
            }
        }
        return C;
    }
};
Mat powmul(Mat A,ll k) {
    Mat B;
    for(int i=1;i<=7;++i) B.mat[i][i]=1;
    while(k) {
        if(k&1) B=B*A;
        A=A*A;
        k>>=1;
    }
    return B;
}
ll solve(ll n,ll a,ll b) {
    if(n==1) return a;
    if(n==2) return b;
    Mat A;
    A.mat[1][1]=A.mat[1][3]=A.mat[1][7]=1;A.mat[1][2]=2;A.mat[1][4]=A.mat[1][6]=4;A.mat[1][5]=6;
    A.mat[2][1]=1;
    A.mat[3][3]=A.mat[3][7]=1;A.mat[3][4]=A.mat[3][6]=4;A.mat[3][5]=6;
    A.mat[4][4]=A.mat[4][7]=1;A.mat[4][5]=A.mat[4][6]=3;
    A.mat[5][5]=A.mat[5][7]=1;A.mat[5][6]=2;
    A.mat[6][6]=A.mat[6][7]=1;
    A.mat[7][7]=1;
    A=powmul(A,n-2);
    ll ans=A.mat[1][1]*b%mod;
    ans=(ans+A.mat[1][2]*a%mod)%mod;
    ans=(ans+A.mat[1][3]*16%mod)%mod;
    ans=(ans+A.mat[1][4]*8%mod)%mod;
    ans=(ans+A.mat[1][5]*4%mod)%mod;
    ans=(ans+A.mat[1][6]*2%mod)%mod;
    ans=(ans+A.mat[1][7])%mod;
    return ans; 
}
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        ///
        ll n,a,b;scanf("%I64d%I64d%I64d",&n,&a,&b);
        ///solve
        printf("%I64d\n",solve(n,a,b));
    }
    return 0;
}