一天四个不同的机器人a、b、c和d在一张跳舞毯上跳舞，这是一张特殊的跳舞毯，他由4个正方形毯子组成一个大的正方形毯子，一开始四个机器人分别站在4 块毯子上，舞蹈的每一步机器人可以往临近（两个毯子拥有同一条边视为临近）的一个毯子移动或停留在原来的毯子（同一块毯子可以有多个机器人停留），这个时 候机器人的制造者你想知道经过n步的移动有多少种方式可以让每个毯子上都有机器人停留。
dp[i][j][k]表示在第i步时，从j走到k的方案数
那么在第i+1步时从j走到k再走到k1的步数即为dp[i]*dp[1]
写出dp[1]求出dp[i]，然后乱搞一下即可
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define MOD 9937
const int INF=0x3f3f3f3f;
const double eps=1e-;
typedef long long ll;
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
const int MAXN=;
int n,m,tt;
ll a[][]=
{
,,,,
,,,,
,,,,
,,,
};
ll dp[][][];
void init()
{
ll k,l,i,j;
for (k=;k<;k++)
{
if (k==)
{
for (i=;i<;i++)
{
for (j=;j<;j++)
{
dp[][i][j]=a[i][j];
}
}
}
else
{
for (i=;i<;i++)
{
for (j=;j<;j++)
{
dp[k][i][j]=;
for (l=;l<;l++)
{
dp[k][i][j]=(dp[k][i][j]+dp[k-][i][l]*a[l][j]%MOD)%MOD;
}
}
}
}
}
}
int main()
{
int i,j,k,ca=;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
init();
while(scanf("%d",&n)!=EOF)
{
ll ans=;
if(n==)
{
printf("1\n");
continue;
}
int w[]={,,,};
while()
{
ans=(ans+(dp[n][][w[]]*dp[n][][w[]]*dp[n][][w[]]*dp[n][][w[]])%MOD)%MOD;
if(!next_permutation(w,w+)) break;
}
printf("%I64d\n",ans);
}
}