【GDOI2018模擬7.12】B

NO IMAGE

Description

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

Input

一行一個整數n

Output

一行一個整數表示答案

Sample Input

1

Sample Output

229

Solution

這題的確是一道水題
你看我都在比賽時想到正解是不是水題

它有3*3的棋盤,也就是由9個點
一個很顯然的想法,算出一個點在走那麼多步的情況下到達另一個點的方案數
設f[i]f[i]為從一個點走到i走了那麼多步的方案數
把和i相鄰的點的方案累計起來即可
步數很多,用矩陣乘法
九個點分別計算,因為轉移過程完全一樣,所以只用矩陣乘法一次就行了
最後,列舉每個點走到哪個點,共9!9!種方法
時間複雜度O(93∗log2(n) 9!)O(9^3*log_2(n) 9!)

Code

#include <cstdio>
#include <algorithm>
#include <cstring>
#define fo(i,a,b) for(int i=a;i<=b;i  )
#define N 10
#define mo 1000000007
#define ll long long
using namespace std;
int dd[5][2]={0,0,1,0,-1,0,0,1,0,-1},e[N],bz[N];
ll ans,d[N][N],a[N][N],b[N][N],c[N][N],n;
int get(int x,int y){return (x-1)*3 y;}
void cl()
{
    fo(i,1,9) fo(j,1,9) c[i][j]=a[i][j],a[i][j]=0;
}
void ch1()
{
    cl();
    fo(i,1,9) fo(j,1,9) fo(k,1,9) a[i][k]=(a[i][k] c[i][j]*b[j][k])%mo;
}
void ch()
{
    cl();
    fo(i,1,9) fo(j,1,9) fo(k,1,9) a[i][k]=(a[i][k] c[i][j]*c[j][k])%mo;
}
void mi(ll x)
{
    if(x<2) return;
    fo(i,1,9) fo(j,1,9) b[i][j]=a[i][j];
    mi(x/2);
    ch();
    if(x%2==1) ch1();
}
void dg(int x)
{
    if(x>9)
    {
        ll an=1;
        fo(i,1,9) an=(an*d[i][e[i]])%mo;
        ans=(ans an)%mo;
        return;
    }
    fo(i,1,9) if(!bz[i]) bz[i]=1,e[x]=i,dg(x 1),bz[i]=0;
}
int main()
{
    scanf("%lld",&n);
    fo(i,1,3) fo(j,1,3)
    {
        fo(k,0,4)
        {
            int x=i dd[k][0],y=j dd[k][1];
            if(x>0&&y>0&&x<4&&y<4)
            {
                a[get(i,j)][get(x,y)]=1;
            }
        }
    }
    mi(n);
    fo(i,1,9) fo(j,1,9) b[i][j]=a[i][j];
    fo(i,1,9)
    {
        memset(a,0,sizeof(a));
        a[1][i]=1;
        ch1();
        fo(j,1,9) d[i][j]=a[1][j];
    }
    ans=0;
    dg(1);
    printf("%lld\n",ans);
}