首先可以想到一个位置状态会从与自己相差不到一行，相差列为奇数的列转移过来，那么很明显对于每一行可以求奇数位置或是偶数位置的前缀和。
设 \(f_{i,j}\) 为跳到第 \(i\) 行第 \(j\) 列的方案数，\(g_{i,j}\) 代表第 \(i\) 行第 \(j\) 列的 \(\sum_{k\ne j(\bmod 1)}f_{i,k}\)，即同行与自己相差奇数列的前缀和。
那么可以写出转移方程。
\(f_{i,j}=g_{i-1,j-1}+g_{i,j-1}+g_{i+1,j-1}\)
\(g_{i,j}=g_{i-2,j}+f_{i,j}\)
这样就可以矩阵加速了，初始矩阵从上到下分别为 \(f_{k,j}\)，\(g_{k,j}\) 和 \(g_{k,j-1}(1\le k\le n)\)。
剩下的转移矩阵在对应位置上加 \(1\) 即可，对此操作如果有疑问可以多去复习下矩阵快速幂。
复杂度：\(O(27n^3\times \log(m))\)。
#include<iostream>
#include<cstdio>
using namespace std;
const int mod=30011;
const int N=105;
struct matrix
{
int x,y,a[155][155];
void init()
{
for(int i=1;i<=x;i++)for(int j=1;j<=y;j++)a[i][j]=0;
}
};
matrix operator *(matrix fi,matrix se)
{
matrix th;
th.x=fi.x,th.y=se.y;
th.init();
for(int i=1;i<=fi.x;i++)
{
for(int j=1;j<=se.y;j++)
{
for(int k=1;k<=fi.y;k++)
{
th.a[i][j]+=fi.a[i][k]*se.a[k][j];
th.a[i][j]%=mod;
}
}
}
return th;
}
matrix quick_pow(matrix x,int y)
{
matrix num=x,sum;
sum.x=sum.y=num.x;
sum.init();
for(int i=1;i<=sum.x;i++)sum.a[i][i]=1;
while(y)
{
if(y&1)sum=sum*num;
num=num*num;
y>>=1;
}
return sum;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
matrix x,y;
x.x=x.y=3*n;
x.init();
y.x=3*n,y.y=1;
y.init();
y.a[1][1]=y.a[1+n][1]=1;
for(int i=1;i<=n;i++)
{
int x1=i+n-1,x2=i+n,x3=i+n+1;
if(x1>n&&x1<=2*n)x.a[i+n][x1]=x.a[i][x1]=1;
if(x2>n&&x2<=2*n)x.a[i+n][x2]=x.a[i][x2]=1;
if(x3>n&&x3<=2*n)x.a[i+n][x3]=x.a[i][x3]=1;
}
for(int i=n+1;i<=2*n;i++)x.a[i][i+n]=1;
for(int i=2*n+1;i<=3*n;i++)x.a[i][i-n]=1;
x=quick_pow(x,m-1);
y=x*y;
printf("%d",y.a[n][1]);
return 0;
}