http://www.51nod.com/Challenge/Problem.html#problemId=1122
如果整体考虑4个机器人会感觉没有头绪,但是如果我们只单独考虑每一个每一个机器人的最终位置,即分别枚举4个机器人的终点(共4!种可能),这样4个机器人到对应终点处的方案数相乘就是答案。
如何求一个机器人从位置i走n步走到位置j的方案数?
a[i][j]=1表示从位置i走1步可以到达位置j
这个矩阵连乘n次,a[i][j]就是从位置i走n步走到位置j的方案数
在本题里,矩阵a为
\[ \begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{bmatrix} \]#include<cstdio>
#include<cstring>
const int mod=1e9+7;
int a[5][5]=
{
0,0,0,0,0,
0,1,1,1,0,
0,1,1,0,1,
0,1,0,1,1,
0,0,1,1,1
};
int ans[5][5],c[5][5];
void mul(int a[5][5],int b[5][5])
{
memset(c,0,sizeof(c));
for(int i=1;i<=4;++i)
for(int j=1;j<=4;++j)
for(int k=1;k<=4;++k)
c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j]%mod)%mod;
for(int i=1;i<=4;++i)
for(int j=1;j<=4;++j)
a[i][j]=c[i][j];
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=4;++i) ans[i][i]=1;
while(n)
{
if(n&1) mul(ans,a);
mul(a,a);
n>>=1;
}
int tot=0;
for(int i=1;i<=4;++i)
for(int j=1;j<=4;++j)
for(int k=1;k<=4;++k)
for(int l=1;l<=4;++l)
if(i!=j && i!=k && i!=l && j!=k && j!=l && k!=l)
tot=(tot+1ll*ans[1][i]%mod*ans[2][j]%mod*ans[3][k]%mod*ans[4][l]%mod)%mod;
printf("%d",tot);
}