自助外贸网站建设,视频分享网站建设,找人做网站注意什么,高端产业主要指哪些领域正题 题目大意 3∗33*33∗3的矩阵上每个格子都有机器人#xff0c;每次可以向相邻格子移动或不动(一个格子上可以有多个机器人)#xff0c;求移动nnn次后每个格子上都有机器人的移动方案数。 解题思路
用矩阵乘法计算出每个格子的机器人移动到每个格子的方案总数。 在枚举最…正题 题目大意
3∗33*33∗3的矩阵上每个格子都有机器人每次可以向相邻格子移动或不动(一个格子上可以有多个机器人)求移动nnn次后每个格子上都有机器人的移动方案数。 解题思路
用矩阵乘法计算出每个格子的机器人移动到每个格子的方案总数。 在枚举最终机器人状态。 之后用矩阵乘法算出来的答案统计这个状态的方案数。 codecodecode
#includecstdio
#includecstring
#define ll long long
#define YMW 1000000007
using namespace std;
ll a[9][9],f[9][9],d[9],n,ans;
bool v[9];
void csh()//初始化移动数组
{memset(f,0,sizeof(f));f[0][1]f[0][3]f[0][0]1;f[2][1]f[2][5]f[2][2]1;f[6][6]f[6][7]f[6][3]1;f[8][8]f[8][5]f[8][7]1;f[1][0]f[1][2]f[1][1]f[1][4]1;f[3][3]f[3][4]f[3][0]f[3][6]1;f[5][5]f[5][2]f[5][4]f[5][8]1;f[7][7]f[7][8]f[7][4]f[7][6]1;f[4][4]f[4][1]f[4][3]f[4][5]f[4][7]1;
}
void mulself()
{ll c[9][9];memset(c,0,sizeof(c));for(ll i0;i9;i)for(ll j0;j9;j)for(ll k0;k9;k)(c[i][j]f[i][k]*f[k][j]%YMW)%YMW;memcpy(f,c,sizeof(f));
}
void mul(ll x)
{ll c[9];memset(c,0,sizeof(c));for(ll i0;i9;i)for(ll j0;j9;j)(c[j]a[x][i]*f[i][j]%YMW)%YMW;memcpy(a[x],c,sizeof(a[x]));
}
void power(ll b,ll x)
{while(b){if(b1) mul(x);mulself();b1;}
}
void dfs(ll dep)
{if(dep9){ll k1;for(ll i0;i9;i)kk*a[i][d[i]]%YMW;ans(ansk)%YMW;return;}for(ll i0;i9;i)if(!v[i]){d[dep]i;v[i]1;dfs(dep1);v[i]0;}
}
int main()
{scanf(%lld,n);for(ll i0;i9;i){a[i][i]1;csh();power(n,i);}dfs(0);printf(%lld,ans);
}
