NC19833（地斗主 ）

思路

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
struct mat{
    int r, c;
    ll a[5][5];
    mat(){
        memset(a, 0, sizeof(a));
    }
    void clear(){
        memset(a, 0, sizeof(a));
    }
};
ll f[5];
ll n, m;
mat mul(mat A, mat B, ll mod){
    mat C;
    C.r = A.r; C.c = B.c;
    for(int i = 1; i <= C.r; i++){
        for(int j = 1; j <= C.c; j++){
            for(int k = 1; k <= A.c; k++){
                C.a[i][j] += A.a[i][k] * B.a[k][j] % mod;
                C.a[i][j] %= mod;
            }
        }
    }
    return C;
}
mat power(mat A, ll b, ll mod){
    mat res;
    res.c = res.r = A.r;
    for(int i = 1; i <= res.r; i++) res.a[i][i] = 1;
    while(b){
        if(b & 1) res = mul(res, A, mod);
        b >>= 1;
        A = mul(A, A, mod);
    }
    return res;
}
ll quick_mod(ll a, ll b, ll mod){
    ll sum = 1;
    while(b){
        if(b & 1) sum = sum * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return sum;
}

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        f[1] = 1; f[2] = 5; f[3] = 11; f[4] = 36;
        scanf("%lld%lld", &n, &m);
        if(n <= 4){
            printf("%lld\n", f[n] % m);
        }
        else{
            mat b;
            b.r = b.c = 4;
            b.a[1][1] = 1; b.a[1][2] = 5; b.a[1][3] = 1; b.a[1][4] = -1;
            b.a[2][1] = 1;
            b.a[3][2] = 1;
            b.a[4][3] = 1;
            mat ans = power(b, n - 4, m);
            ll gg = (((ans.a[1][1] * f[4] % m + ans.a[1][2] * f[3] % m) % m + ans.a[1][3] * f[2] % m) % m + ans.a[1][4] * f[1] % m) % m;
            while(gg < 0) gg += m;
            printf("%lld\n", gg % m);
        }
    }
    return 0;
}