地斗主

题意：
给你一个4 * n的矩阵，让你用1 * 2的矩阵填满，求有多少种方法？

思路：
n=1时有1种
n=2时有5种
n=3时有11种
n=4时有36种
由官方题解可知dp[i]=dp[i-1]+5d[i-2]+dp[i-3]-dp[i-4].
所以我们可以用矩阵快速幂求结果。

为了防止产生负数，所以-1可以等价于需要模的数-1。
*代码：**

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

ll inf=998244353;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

ll s[4][4], p[4][4], a[4][4];

void che()
{
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            p[i][j]=0;
            for(int o=0;o<4;o++)
            {
                p[i][j]=(p[i][j]+s[i][o]*a[o][j])%inf;
            }
        }
    }
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            s[i][j]=p[i][j];
        }
    }
}

void che1()
{
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            p[i][j]=0;
            for(int o=0;o<4;o++)
            {
                p[i][j]=(p[i][j]+a[i][o]*a[o][j])%inf;
            }
        }
    }
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            a[i][j]=p[i][j];
        }
    }
}

void juqow(int m)
{
    while(m)
    {
        if(m&1)
        {
            che();
        }
        che1();
        m>>=1;
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n, k;
        scanf("%d%d",&n,&k);
        inf=k;
        memset(s,0,sizeof(s));
        memset(a,0,sizeof(a));
        a[0][0]=1;
        a[0][1]=5;
        a[0][2]=1;
        a[0][3]=inf-1;
        a[1][0]=1;
        a[2][1]=1;
        a[3][2]=1;
        for(int i=0;i<=4;i++)
        {
            s[i][i]=1;
        }
        if(n==1)
        {
            printf("1\n");
        }
        else if(n==2)
        {
            printf("5\n");
        }
        else if(n==3)
        {
            printf("11\n");
        }
        else if(n==4)
        {
            printf("36\n");
        }
        else
        {
            juqow(n-4);
            printf("%lld\n",(36*s[0][0]+s[0][1]*11+s[0][2]*5+s[0][3]*1)%inf);
        }
    }
    return 0;
}