每如一题 8月13日地斗主 1*2矩阵覆盖 矩阵快速幂

题目链接：https://ac.nowcoder.com/acm/problem/19833
题目大意：

思路：一看就有递推关系：
f[n]:填满n行的方案数
把前几项画出来，就是：


然后矩阵快速幂就可以了。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
int mod=1e9+7;

struct mat {
    LL m[4][4];
};

struct mat_qpow {
    //矩阵乘法
    //(AB)[i][j]=A[i][1]*B[1][j]+A[i][2]*B[2][j]+...+A[i][k]*B[k][j] (0<k<n)
    //矩阵乘法(剪枝)
    mat msub(mat a, mat b, LL n) {
        mat ret;
        memset(&ret,0,sizeof(ret));
        for(int i=0; i<n; i++)
            for(int k=0; k<n; k++) {
                if(a.m[i][k]==0) {
                    continue;
                }
                for(int j=0; j<n; j++) {
                    ret.m[i][j]=(a.m[i][k]*b.m[k][j]%mod+ret.m[i][j]+mod)%mod;
                }
            }

        return ret;

    }

    void unit(mat &a, LL n) {
        for(int i=0 ; i<n; i++) {
            a.m[i][i]=1;
        }
    }

    //矩阵a^n
    mat qpow(mat a, LL x, LL n) { //快速幂
        mat ans;
        memset(&ans, 0, sizeof(ans));
        unit(ans, n);//初始化
        while(x) {
            if(x&1)
                ans=msub(ans,a, n);
            a=msub(a, a, n);
            x>>=1;
        }
        return ans;
    }

} T;

int main() {

    int t;
    scanf("%d", &t);
    while(t--) {
        int n, m;
        scanf("%d%d", &n, &m);
        mod=m;
        mat A={
            1, 5, 1, -1,
            1, 0, 0, 0,
            0, 1, 0, 0,
            0, 0, 1, 0
        };

        mat B= {
            36, 0, 0, 0,
            11, 0, 0, 0,
            5,  0, 0, 0,
            1,  0, 0, 0
        };
        if(n<=4) {
            printf("%lld\n", B.m[4-n][0]%mod);
        } else {
            mat C=T.qpow(A, n-4, 4);
            C=T.msub(C, B, 4);
            printf("%lld\n", C.m[0][0]%mod);
        }

    }

    return 0;
}