HihoCoder 1504 : 骑士游历 (矩阵乘法)

时间：2022-09-18 05:16:38

描述

在8x8的国际象棋棋盘上给定一只骑士（俗称“马”）棋子的位置(R, C)，小Hi想知道从(R, C)开始移动N步一共有多少种不同的走法。

输入

第一行包含三个整数，N，R和C。

对于40%的数据， 1 <= N <= 1000000

对于100%的数据， 1 <= N <= 1000000000 1 <= R, C <= 8

输出

从(R, C)开始走N步有多少种不同的走法。由于答案可能非常大，你只需要输出答案模1000000007的余数。

样例输入

2 1 1

样例输出

12

此类题在Floyd算法里用到过，即问从a出发，走x步，有多少种方法到b点。 充分利用floyd和矩阵的相似性（3个for语句），就可以求出。

很久没有写矩阵了，温故一下。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=;

#define ll long long

const int Mod=1e9+;

int x[]={,,-,-,,,-,-};

int y[]={,-,,-,,-,,-};

struct mat

{

    ll M[maxn][maxn];

    mat() { memset(M,,sizeof(M)); }

    mat friend operator *(mat a,mat b)

    {

        mat res;

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

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

          for(int j=;j<=;j++){

                res.M[i][j]=(res.M[i][j]+a.M[i][k]*b.M[k][j])%Mod;

         } return res;

    }

    mat friend operator ^(mat a,int x)

    {

       mat res; for(int i=;i<=;i++) res.M[i][i]=;

       while(x){

            if(x&) res=a*res; a=a*a; x/=;

       } return res;

    }

};    

mat base;

void prepare()

{

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

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

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

        if(i+x[k]>=&&i+x[k]<=&&j+y[k]>=&&j+y[k]<=)

          base.M[(i-)*+j][(i+x[k]-)*+j+y[k]]=;

}

int main()

{

    int N,R,C,ans=;

    scanf("%d%d%d",&N,&R,&C);

    prepare();

    base=base^N;

    for(int i=;i<=;i++)  ans=(ans+base.M[(R-)*+C][i])%Mod;

    printf("%d\n",ans);

    return ;

}

相关文章