地斗主

题意

用 的骨牌去填充 的矩阵，问有几种方法。

分析

手算一下前五项，可以得到这么一个序列：1,5，11，36，95

设 表示拼完前 i 列的方案数。这时考虑 OEIS 。可以得到递推式：

然后利用矩阵快速幂就可以解决了。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define int long long

struct mat
{
    int a[4][4];
    mat(){mem(a,0);}
};

mat mul(mat a,mat b,int M)
{   
    mat res;
    for(int i = 0; i < 4; i++) 
    {
        for(int j = 0; j < 4; j++) 
        {
            for(int k = 0; k < 4; k++)
            {
                res.a[i][j] += a.a[i][k]*b.a[k][j]%M;
                res.a[i][j] += M;
                res.a[i][j] %= M;
            }
        }
    }
    return res;
}

mat solve(int k,int M)
{
    mat res;
    res.a[0][0] = 1;res.a[0][1] = 5;res.a[0][2] = 1;res.a[0][3] = -1;
    res.a[1][0] = 1;res.a[2][1] = 1;res.a[3][2] = 1;
    mat ans;
    ans.a[0][0] = 36;ans.a[1][0] = 11;ans.a[2][0] = 5;ans.a[3][0] = 1;
    while(k)
    {
        if(k&1) ans = mul(res,ans,M);
        res = mul(res,res,M);
        k >>= 1;
    }
    return ans;
}

signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    int T;cin>>T;
    int a[] = {1,1,5,11};
    while(T--)
    {   
        int n,m;
        cin>>n>>m;
        if(n >= 4)
        {
            mat res = solve(n-4,m);
            cout<<res.a[0][0]<<endl;
        }
        else
        {
            cout<<a[n]%m<<endl;
        }
    }
    return 0;
}