BZOJ-4417: [Shoi2013]超级跳马

Description

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

设dp[i][j]表示到第i列第j行位置的方案数。
得：
我们发现dp[i-2][j]好像有很棒的性质啊。。。
化简：dp[i][j]=dp[i-2][j]+dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1]
一看m那么大，分块矩乘。大小为100。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod=30011;
int n,m,M;
struct matrix
{
    int a[105][105];
    matrix(){memset(a,0,sizeof a);}
    matrix operator *(const matrix z)
    {
        matrix ret;
        for(int i=1;i<=M;++i)
            for(int j=1;j<=M;++j)
                for(int k=1;k<=M;++k)
                    ret.a[i][j]=(ret.a[i][j]+a[i][k]*z.a[k][j])%mod;
        return ret;
    }
};
struct matrix_f
{
    int f[105];
    matrix_f(){memset(f,0,sizeof f);}
    matrix_f operator *(const matrix z)
    {
        matrix_f ret;
        for(int j=1;j<=M;++j)
            for(int k=1;k<=M;++k)
                ret.f[j]=(ret.f[j]+f[k]*z.a[k][j])%mod;
        return ret;
    }
    void output()
    {
        for(int i=1;i<=M;++i) printf("%d ",f[i]); puts("");
    }
};
matrix_f ans;
matrix base;
int main()
{
    scanf("%d%d",&n,&m); M=n<<1;
    ans.f[1]=1; if(n>1) ans.f[2]=1;
    for(int i=1;i<=n;++i)
    {
        base.a[i+n][i]=1;
        base.a[i][i+n]=1;
        if(i!=1) base.a[i-1][i]=1;
        base.a[i][i]=1;
        if(i!=n) base.a[i+1][i]=1;
    }
    m-=2;
    while(m)
    {
        if(m&1) ans=ans*base;
        base=base*base; m>>=1;
    }
    // ans.output();
    printf("%d\n",ans.f[n]);
    return 0;
}