题目概述

现有一个 $n$ 行 $m$ 列的棋盘，一只马欲从棋盘的左上角跳到右下角。每一步它向右跳奇数列，且跳到本行或相邻行。跳越期间，马不能离开棋盘。试求跳法种数 $mod\ 30011$ 。

解题报告

我好菜啊，怎么这都不会啊，Orz ChesterKing。首先先写柿子：

$$ f_{i,j}=\sum_{k}f_{i-(2k-1),j-1}+f_{i-(2k-1),j}+f_{i-(2k-1),j+1} $$

$m$ 这么大应该是矩乘，但是这样肯定没法做啊QAQ。我们要想办法把这个柿子变成只和相邻几个有关，怎么办呢？想削掉 $\Sigma$ 当然只能记录前缀和啦XD。

所以记录 $sum_{0/1,j}$ 表示当前前面和后面的两列前缀和，转移：

$$ sum'_{0,i}=sum_{1,i}\\ sum'_{1,i}=sum_{0,i}+sum_{1,i-1}+sum_{1,i}+sum_{1,i+1} $$

这样就可以矩乘搞了。

示例程序

#include<cstdio>
using namespace std;
const int maxn=100,MOD=30011;

int n,m;
struct Matrix{
    int r,c,s[maxn][maxn];
    inline void zero(int n,int m) {r=n;c=m;for (int i=0;i<n;i++) for (int j=0;j<m;j++) s[i][j]=0;}
    inline void unit(int n) {zero(n,n);for (int i=0;i<n;i++) s[i][i]=1;}
};
Matrix f,T;
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline Matrix operator * (const Matrix &a,const Matrix &b){
    static Matrix c;c.zero(a.r,b.c);
    for (int i=0;i<a.r;i++)
        for (int j=0;j<b.c;j++)
            for (int k=0;k<a.c;k++)
                AMOD(c.s[i][j],a.s[i][k]*b.s[k][j]%MOD);
    return c;
}

#define ID(x,y) ((x)*n+(y)-1)
inline Matrix Pow(Matrix w,int b){
    static Matrix s;s.unit(w.r);
    while (b) {if (b&1) s=s*w;b>>=1;if (b) w=w*w;}
    return s;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);T.zero(n<<1,n<<1);
    for (int i=1;i<=n;T.s[ID(1,i)][ID(0,i)]++,T.s[ID(0,i)][ID(1,i)]++,i++)
        for (int j=(i-1<1?1:i-1);j<=i+1&&j<=n;j++)
            T.s[ID(1,j)][ID(1,i)]++;
    f.zero(1,n<<1);f.s[0][ID(1,1)]++;f=f*Pow(T,m-2);
    int ans=MOD-f.s[0][ID(0,n)];f=f*T;AMOD(ans,f.s[0][ID(1,n)]);
    return printf("%d\n",ans),0;
}