NC19833 地斗主(矩阵快速幂)

题目链接

题意：



题解：















AC代码

/*
    Author : zzugzx
    Lang : C++
    Blog : blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
#define mem(a, b) memset(a, b, sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod = 1e9 + 7;
//const int mod = 998244353;

const double eps = 1e-6;
const double pi = acos(-1.0);
const int maxn = 1e6 + 10;
const int N = 1e2 + 5;
const ll inf = 0x3f3f3f3f;
const int dir[][2]={{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
int mod;
ll Pow(ll a, ll b){
    ll ans = 1;
    while(b > 0){
        if(b & 1){
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
ll inv(ll b){
    return Pow(b,mod-2)%mod;
}
class mat {
public:
    int n,m;
    ll v[N][N], is[N], js[N];
    mat(int n,int m) : n(n), m(m){ memset(v, 0, sizeof(v));}
    void init() {
        memset(v, 0, sizeof(v));
    }
    void init1() {
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                v[i][j] = (i == j); //单位矩阵
    }
    mat operator * (const mat B) const {//矩阵乘法 A(n,k)*B(k,m)=C(n,m);
        mat C(n, B.m);
        C.init();
        for(int i = 0; i < n; i++)
        for(int j = 0; j < B.m; j++)
        for(int k = 0; k < m; k++)
            C.v[i][j] = (C.v[i][j]+v[i][k]*B.v[k][j]) % mod;//Mod
        return C;
    }
    mat operator ^ (int t)//矩阵快速幂 n=m时可用
    {
        mat ans(n, n), now(n, n);
        ans.init1();
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                now.v[i][j] = v[i][j];
        while(t > 0) {
            if(t & 1) ans = ans * now;
            now = now * now;
            t >>= 1;
        }
        return ans;
    }
    void change() { // 转置
        swap(n, m);
        for(int i = 0; i < max(n, m); i++) {
            for(int j = i + 1; j < max(n, m); j++) {
                swap(v[i][j], v[j][i]);
            }
        }
    }
    void Minv() {  // 逆矩阵
        for(int k = 0; k < n; k++) {
            for(int i = k; i < n; i++) // 1
                for(int j = k; j < n; j++)
                    if(v[i][j]) {
                        is[k] = i;
                        js[k] = j;
                        break;
                    }
            for(int i = 0; i < n; i++) // 2
                swap(v[k][i], v[is[k]][i]);
            for(int i = 0; i < n; i++)
                swap(v[i][k], v[i][js[k]]);
            v[k][k] = inv(v[k][k]); // 3
            for(int j = 0; j < n; j++)
                if(j != k) // 4
                    v[k][j] = v[k][j] * v[k][k] % mod;
            for(int i = 0; i < n; i++)
                if(i != k) // 5
                for(int j = 0; j < n; j++)
                    if(j != k)
                        v[i][j] = (v[i][j] + mod - v[i][k] * v[k][j] % mod) % mod;
            for(int i = 0; i < n; i++)
                if(i != k)
                v[i][k] = (mod - v[i][k] * v[k][k] % mod) % mod;
        }
        for(int k = n - 1; k >= 0; k--) { // 6
            for(int i = 0; i < n; i++)
                swap(v[js[k]][i], v[k][i]);
            for(int i = 0; i < n; i++)
                swap(v[i][is[k]], v[i][k]);
        }
    }
};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
    int _;
    cin >> _;
    while (_--) {
        mat A(4, 1), B(4, 4);
        B.v[0][0] = B.v[0][2] = 1;
        B.v[0][1] = 5, B.v[0][3] = -1;
        B.v[1][0] = B.v[2][1] = B.v[3][2] = 1;
        A.v[0][0] = 36, A.v[1][0] = 11;
        A.v[2][0] = 5, A.v[3][0] = 1;
        int n;
        cin >> n >> mod;
        if (n <= 4) cout << A.v[4 - n][0] << endl;
        else {
            mat C = (B ^ (n - 4)) * A;
            cout << (C.v[0][0] + mod) % mod << endl;
        }
    }
    return 0;
}