记录编号	584884	评测结果	AAAAAAAAAA
题目名称	选拔队员	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.098 s
提交时间	2023-11-16 19:04:54	内存使用	6.83 MiB

#include <bits/stdc++.h>
using namespace std;
int t,mod,n;
struct Matrix{
    int a[3][3],n,m;
    void clear(){n = m = 0;memset(a,0,sizeof(a));}
    Matrix operator * (const Matrix &x)const{
        Matrix y;y.clear();
        y.n = n,y.m = m;
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= m;j++)
                for(int k = 1;k <= m;k++)
                    y.a[i][j] = (y.a[i][j] + (a[i][k] * x.a[k][j]) % mod) % mod;
        return y;
    }
}c,f;
int main(){
    freopen("seata.in","r",stdin);
    freopen("seata.out","w",stdout);
    scanf("%d%d",&t,&mod);
    while(t--){
        scanf("%d",&n);
        if(n == 1){printf("%d\n",2%mod);continue;}
        if(n == 2){printf("%d\n",3%mod);continue;}
        n -= 2;
        c.clear();f.clear();
        f.n = 1,f.m = 2;
        f.a[1][1] = 3,f.a[1][2] = 2;
        c.n = c.m = 2;
        c.a[1][1] = 1,c.a[2][1] = 1,c.a[1][2] = 1;
        while(n){
            if(n & 1)f = f * c;
            c = c * c;
            n >>= 1;
        }
        printf("%d\n",f.a[1][1] % mod);
    }
    
    return 0;
    
}