Problem Description
一天四个不同的机器人a、b、c和d在一张跳舞毯上跳舞，这是一张特殊的跳舞毯，他由4个正方形毯子组成一个大的正方形毯子，一开始四个机器人分别站在4块毯子上，舞蹈的每一步机器人可以往临近（两个毯子拥有同一条边视为临近）的一个毯子移动或停留在原来的毯子（同一块毯子可以有多个机器人停留），这个时候机器人的制造者你想知道经过n步的移动有多少种方式可以让每个毯子上都有机器人停留。
Input
对于每组数据输入一个整数n(0<=n<=100)
Output
对于每组输入输出一个整数表示方法种数，种数可能很大请对9937取模。
Sample Input
1
Sample Output
9
http://www.aiuxian.com/article/p-1247157.html
可以用一个四位的五进制表示每块毯上有多少个机器人
把这个四位四进制压缩成一个数j
dp[i][j]代表走了i步之后四块毯上人的状态上j的情况有多少种
最后dp[n][1*5*5*5+1*5*5+1*5+1]就是答案
复杂度100*5的4次方*5的4次方
此题还可以扩展,比如步数N<=1000000000这个时候要用矩阵的快速幂来做.
这里没有出这种数据,我就没有写了.
AC code
#include
#include
const int MOD=9937;
const int MAX=5*5*5*5;
const int TAG=5*5*5+5*5+5+1;
int c[5][5]={0};
int path[MAX][MAX]={0};
int b[4]={0},t[4]={0};
int dp[101][MAX]={0};
void split(int n)
{
int i;
for(i=0;i {
b[i]=n%5;
n/=5;
}
}
void DFS(int deep,int state,int sum)
{
int i,j;
if(deep==4)
{
j=0;
for(i=3;i>=0;i--)
{
j=j*5+t[i];
}
path[state][j]+=sum;
if(path[state][j]>=MOD)path[state][j]-=MOD;
return ;
}
for(i=0;i<=b[deep];i++)
{
for(j=0;j+i<=b[deep];j++)
{
t[(deep+1)%4]+=i;
t[(deep-1+4)%4]+=j;
t[deep]+=b[deep]-i-j;
DFS(deep+1,state,sum*c[b[deep]][i]*c[b[deep]-i][j]%MOD);
t[(deep+1)%4]-=i;
t[(deep-1+4)%4]-=j;
t[deep]-=b[deep]-i-j;
}
}
}
int main()
{
int i,j,k,n,sum;
for(i=0;i {
for(j=0;j {
if(i==j||j==0)c[i][j]=1;
else c[i][j]=c[i-1][j-1]+c[i-1][j];
if(c[i][j]>=MOD)c[i][j]-=MOD;
}
}
//puts("ok1");
for(i=0;i {
//printf("%d\n",i);
split(i);
if(b[0]+b[1]+b[2]+b[3]>4)continue;
memset(t,0,sizeof(t));
DFS(0,i,1);
}
//puts("ok2");
dp[0][TAG]++;
for(i=0;i+1<101;i++)
{
for(j=0;j<(MAX);j++)
{
if(dp[i][j]==0)continue;
for(k=0;k<(MAX);k++)
{
dp[i+1][k]+=dp[i][j]*path[j][k];
dp[i+1][k]%=MOD;
}
}
}
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",dp[n][TAG]);
}
return 0;
}