[矩阵快速幂] AcWing 206 石头游戏

发表于 更新于 分类于 阅读次数： 本文字数： 3.3k 阅读时长 ≈ 3 分钟

别告诉我你不知道什么是矩阵乘法 (╯▽╰)
题目传送门

看到题目，第一反应以为是模拟水题。结果一看数据范围1e81e8…

模拟看来是不行了，需要想复杂度更优的解法

考虑矩阵乘法
把n×mn \times m的矩阵映射到一个含有 nmnm 个元素的行向量
我们可以尝试构造新的状态转移矩阵 aa，其行数和列数均为 nmn m，每次操作就相当于把一个1×nm1 \times nm的矩阵（每个格子里石子的数量）和状态转移矩阵相乘

令a[0][0]=1a[0][0]=1
如果操作是EE，相当于把它右面的元素加上它的值，即 a[id(i,j)][id(i-1,j)]=1 （id(i,j)id(i,j)表示第ii行jj列元素在映射中的位置）；W,S,EW,S,E同理
如果操作是数字，就转移成 a[id(i,j)][id(i,j)]=1; a[0][id(i,j)]=x;（相当于保留原来的数字，同时加上新的数字 xx）
如果操作是 DD，不用管，置空即可

此外，题目中有一个隐含条件，如果试图把石子放到不存在的格子里的话，把它当成 DD 即可，所以要判断格子是否在边界处

操作序列长度不超过66，所以状态转移矩阵一定会有循环节且循环节不超过 lcm(1,2,3,4,5,6)=60lcm(1,2,3,4,5,6)=60
因此我们只需要计算出前6060个转移矩阵
求出前6060个矩阵的乘积，利用矩阵快速幂来求解乘积的⌊t60⌋\lfloor \frac{t}{60} \rfloor次方，剩下的t%60t\%60个可以直接暴力乘上去，就可以愉快地求出最终tt秒时的状态转移矩阵啦

注意一点，数据范围会爆intint，注意开long longlong~long

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//ʯͷÓÎÏ·--¾ØÕó¿ìËÙÃÝ 
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,m,t,act,r[70];
char op[15][15];
struct Matrix{
    int n,m;
    ll a[70][70];
    Matrix operator*(const Matrix& rhs)const{    //矩阵乘法
        Matrix ans;
        memset(&ans,0,sizeof(ans));
        ans.n=n,ans.m=rhs.m;
        for(int i=0;i<=ans.n;i++){
            for(int j=0;j<=ans.m;j++){
                for(int k=0;k<=m;k++)
                    ans.a[i][j]+=a[i][k]*rhs.a[k][j];
            }
        }
        return ans;
    }
    Matrix() {n=m=0;memset(a,0,sizeof(a));}
    void operator*=(const Matrix& rhs) {*this=*this*rhs;}
};
Matrix qpow(Matrix x,int y){    //矩阵快速幂
    Matrix ans;
    memset(&ans,0,sizeof(ans));
    ans.n=ans.m=x.n;
    for(int i=0;i<=n*m;i++) ans.a[i][i]=1;
    while(y){
        if(y&1) ans*=x;
        x*=x; y>>=1;
    }
    return ans;
}
int id(int x,int y) {return (x-1)*m+y;}    //建立映射
int mod(int x,int y){return x%y?x%y:y;}
signed main(){
    scanf("%d%d%d%d",&n,&m,&t,&act);
    {
        char tmp[15];
        for(int i=1;i<=n;i++){
            scanf("%s",tmp+1);
            for(int j=1;j<=m;j++) r[id(i,j)]=tmp[j]-'0'+1;    //每个格子对应的操作序列编号
        }
    }
    for(int i=1;i<=act;i++) scanf("%s",op[i]+1);
    
    /* computing */
    Matrix tt[65];    //1~60的状态转移矩阵
    memset(tt,0,sizeof(tt));
    for(int i=1;i<=60;i++){            //for 1 to 60 sec(matrix)
        tt[i].n=tt[i].m=n*m;
        tt[i].a[0][0]=1;
        for(int j=1;j<=n;j++){        //for line 1 to n
            for(int k=1;k<=m;k++){    //for col 1 to n
                char cop=op[r[id(j,k)]][mod(i,strlen(op[r[id(j,k)]]+1))];
                if(cop=='N'&&j>1) tt[i].a[id(j,k)][id(j-1,k)]=1;
                else if(cop=='W'&&k>1) tt[i].a[id(j,k)][id(j,k-1)]=1;
                else if(cop=='S'&&j<n) tt[i].a[id(j,k)][id(j+1,k)]=1;
                else if(cop=='E'&&k<m) tt[i].a[id(j,k)][id(j,k+1)]=1;
                else if(isdigit(cop)){    //指令是数字
                    tt[i].a[id(j,k)][id(j,k)]=1;
                    tt[i].a[0][id(j,k)]=cop-'0';
                }
            }
        }
    }
    
    Matrix eps;        //前60个矩阵的乘积
    eps.n=eps.m=n*m;
    for(int i=0;i<=eps.n;i++) eps.a[i][i]=1;
    for(int i=1;i<=60;i++) eps*=tt[i];

    Matrix final;    //前t个矩阵的乘积
    final.n=final.m=n*m;
    final=qpow(eps,t/60);
    for(int i=1;i<=t%60;i++) final*=tt[i];
    
    Matrix original;    //石子矩阵
    original.n=1,original.m=n*m;
    original.a[1][0]=1;
    original*=final;
    
    ll ans=0;
    for(int i=1;i<=n*m;i++) ans=max(ans,original.a[1][i]);
    printf("%lld\n",ans);
    return 0;
}