发现只要有思路还是比较好切题的。
相信大家不出意外，对于下面这个矩阵还是好构造的。
第0排代表第0号格子的机器人，可以到达个格子，可见2号格子是不可达的。
这个矩阵的N次幂，就是机器人走多少步形成的局面。
上面矩阵的2次幂：
可以得到上面的矩阵，这是什么意思呢？
第0排的3表示0号格子的机器人通过2步有3种方法到0号格子。
哪三种？0-0-0,0-1-0,0-3-0。就这三种。
同样每个格子的数也代表了不同的意义。
那么题中所求的最终回到每个格子一个机器人的状态。
也就是在这个矩阵中不同行不同列放置4个机器人的总数，so...
用dfs就可以了。....ac
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;struct node
{int m[4][4];
}res,temp,mod;int sum;node matriXmult( node a,node b )
{node c;memset( c.m,0,sizeof(c.m) );for( int i=0;i<4;i++ )for( int j=0;j<4;j++ )for( int k=0;k<4;k++ )c.m[i][j]+=a.m[i][k]*b.m[k][j];for( int i=0;i<4;i++ )for( int j=0;j<4;j++ )c.m[i][j]%=9937;return c;
}void matrix_Power(int n)
{memset( res.m,0,sizeof(res.m) );memset( temp.m,0,sizeof(temp.m) );for( int i=0;i<4;i++ ){res.m[i][i]=1;for( int j=0;j<4;j++ )temp.m[i][j]=mod.m[i][j];}for( int i=0;i<31;i++ ){if( n&(1<<i) )res=matriXmult(res,temp);temp=matriXmult(temp,temp);}
}bool vis[4];
void dfs( int col,int row,int x )
{if( x==0 )return ;x=(x*res.m[row][col])%9937;if( row>2 )sum=(sum+x)%9937;for( int i=0;i<4;i++ ){if( vis[i]==false ){vis[i]=true;dfs( i,row+1,x );vis[i]=false;}}
}int main()
{int n;for( int i=0;i<4;i++ )for( int j=0;j<4;j++ )mod.m[i][j]=1;mod.m[0][2]=0;mod.m[1][3]=0;mod.m[2][0]=0;mod.m[3][1]=0;while( scanf("%d",&n)!=EOF ){matrix_Power(n);sum=0;int x;memset( vis,0,sizeof(vis) ); for( int i=0;i<4;i++ ){x=1;vis[i]=true;dfs( i,0,x );vis[i]=false;}printf( "%d\n",sum );}return 0;
}