【GDOI2018模擬7.12】B 矩陣乘法 dp

NO IMAGE

Description

給定一個3*3的網格圖,一開始每個格子上都站著一個機器人。每一步機器人可以走到相鄰格子或留在原地,同一個格子上可以有多個機器人。問走n步後,有多少種走法,滿足每個格子上都有機器人。答案對10^9 7取模。

Input

1

Output

229

這題是個大水但是我由於沉迷第一題無法自拔導致沒有切= =
設f[i][j]表示從i走到j的方案數,一開始先預處理走一步的,然後我乘以n次,就是走n步的方案數,然後9!列舉每一個位置上的機器人原來在哪裡(編號),然後就可以了。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define fo(i,a,b) for(int i=a;i<=b;i  )
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=1e5 5;
const int mo=1e9 7;
typedef long long ll;
ll n;
int ans,f[20][20];
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
bool vis[10];
int t[10];
struct matrix
{
int a[10][10];
inline void init(int n)
{
memset(a,0,sizeof(a));
fo(i,1,n)a[i][i]=1;
}
inline void clear()
{
memset(a,0,sizeof(a));
}
}a;
inline int trans(int x,int y)
{
return (x-1)*3 y;
}
inline void mul(matrix &c,matrix a,matrix b)
{
c.clear();
fo(i,1,9)
fo(j,1,9)
fo(k,1,9)
{
c.a[i][j]=(c.a[i][j] 1ll*a.a[i][k]*b.a[k][j]%mo)%mo;
}
}
inline matrix pow(matrix x,ll b)
{
matrix ans;
ans.init(9);
while (b)
{
if (b&1)mul(ans,ans,x);
mul(x,x,x);
b>>=1;
}
return ans;
}
inline int calc()
{
int ans=1;
fo(i,1,9)ans=1ll*ans*f[i][t[i]]%mo;
return ans;
}
inline void dfs(int x)
{
if (x>9)
{
ans=(ans calc())%mo;
return;
}
fo(i,1,9)
if (!vis[i])t[x]=i,vis[i]=1,dfs(x 1),vis[i]=0;
}
int main()
{
scanf("%lld",&n);
fo(i,1,3)
fo(j,1,3)
{
a.a[trans(i,j)][trans(i,j)]=1;
fo(k,0,3)
{
int x=i dx[k];
int y=j dy[k];
if (x<1||x>3||y<1||y>3)continue;
a.a[trans(x,y)][trans(i,j)]=1;
}
}
a=pow(a,n);
fo(i,1,9)
fo(j,1,9)
f[i][j]=a.a[i][j];
dfs(1);
printf("%d\n",ans);
return 0;
}