P3990 [SHOI2013]超级跳马

题目描述

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

试求跳法种数\(\bmod 30011\)。

输入输出格式

输入格式：

仅有一行，包含两个正整数\(n, m\)，表示棋盘的规模。

输出格式：

仅有一行，包含一个整数，即跳法种数\(\bmod 30011\)。

说明

对于\(10\%\)的数据，\(1 ≤ n ≤ 10\)，\(2 ≤ m ≤ 10\)；

对于\(50\%\)的数据，\(1 ≤ n ≤ 10\)，\(2 ≤ m ≤ 10^5\)；

对于\(80\%\)的数据，\(1 ≤ n ≤ 10\)，\(2 ≤ m ≤ 10^9\)；

对于\(100\%\)的数据，\(1 ≤ n ≤ 50\)，\(2 ≤ m ≤ 10^9\)。

发现我的做法有点诡异...

思路：首先我们只考虑从左边某一列的转移，显然可以构造这样的一个转移矩阵

然后设这个转移矩阵为\(T\)，设第\(i\)列的答案矩阵为\(A_i\)

则\(A_n=T*(A_{n-1}+A_{n-3}+A_{n-5}+\dots)\)

\(A_{n-2}=T*(A_{n-3}+A_{n-5}+A_{n-7}+\dots)\)

那么有\(A_n=T*A_{n-1}+A_{n-2}\)，发现这是个递推，于是再次构造矩阵加速转移

然后大力搞就行了，复杂度\(O(2^3n^3\log t)\)

注意一点\(A_3=TA_2\)不符合递推式

Code:

#include <cstdio>

#include <cstring>

const int mod=30011;

int n,m;

struct matrix1

{

    int dx[52][52];

    matrix1(){memset(dx,0,sizeof(dx));}

    matrix1 friend operator *(matrix1 n1,matrix1 n2)

    {

        matrix1 n3;

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

                for(int k=1;k<=n;k++)

                    (n3.dx[i][j]+=n1.dx[i][k]*n2.dx[k][j])%=mod;

        return n3;

    }

    matrix1 friend operator +(matrix1 n1,matrix1 n2)

    {

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

                (n1.dx[i][j]+=n2.dx[i][j])%=mod;

        return n1;

    }

};

struct matrix2

{

    matrix1 dx[3][3];

    matrix2(){matrix1();}

    matrix2 friend operator *(matrix2 n1,matrix2 n2)

    {

        matrix2 n3;

        for(int i=1;i<=2;i++)

            for(int j=1;j<=2;j++)

                for(int i1=1;i1<=n;i1++)

                    for(int j1=1;j1<=n;j1++)

                        n3.dx[i][j].dx[i1][j1]=0;

        for(int i=1;i<=2;i++)

            for(int j=1;j<=2;j++)

                for(int k=1;k<=2;k++)

                    n3.dx[i][j]=n3.dx[i][j]+n1.dx[i][k]*n2.dx[k][j];

        return n3;

    }

}S,T,F;

int main()

{

    scanf("%d%d",&n,&m);

    S.dx[1][1].dx[1][1]=S.dx[1][1].dx[2][1]=1;

    for(int i=1;i<=n;i++)

    {

        T.dx[1][2].dx[i][i]=T.dx[2][1].dx[i][i]=1;

        T.dx[1][1].dx[i][i]=T.dx[1][1].dx[i][i-1]=T.dx[1][1].dx[i][i+1]=1;

    }

    if(m==2) return printf("%d\n",S.dx[1][1].dx[n][1]),0;

    m-=3,F=T;

    while(m)

    {

        if(m&1) F=F*T;

        T=T*T;

        m>>=1;

    }

    S=F*S;

    printf("%d\n",S.dx[1][1].dx[n][1]);

    return 0;

}

2018.12.19