权限题。
描述
石头游戏在一个 n 行 m 列 (1≤n,m≤8) 的网格上进行，每个格子对应一种操作序列，操作序列至多有10种，分别用0~9这10个数字指明。
操作序列是一个长度不超过6且循环执行、每秒执行一个字符的字符串。每秒钟，所有格子同时执行各自操作序列里的下一个字符。序列中的每个字符是以下格式之一：
数字09：表示拿09个石头到该格子。
NWSE：表示把这个格子内所有的石头推到相邻的格子，N表示上方，W表示左方，S表示下方，E表示右方。
D：表示拿走这个格子的所有石头。
给定每种操作序列对应的字符串，以及网格中每个格子对应的操作序列，求石头游戏进行了 t 秒之后，石头最多的格子里有多少个石头。在游戏开始时，网格是空的。
SimpleInput:
1 6 10 3
011112
1E
E
0
SimpleOutput
3
Solution:
首先 不妨把n×m的网格压成一行，方便接下来的转移，并设id(i,j)为i,j在序列中的位置。
其次 由于操作序列长度不超过6，那么由于lcm(1,2,3,4,5,6)=60，所以每60次操作后，操作序列的状态又会回到初始态。
那么 这启示着：如果想把操作序列状态存下来只需要记录60种即可。
所以 考虑把每一种状态存入矩阵。
然后对应的进行一下转移，用矩阵快速幂加速即可。
关于矩阵的构造，有一个很巧妙的是：增加一个第0行/列。
在状态矩阵中，第0行代表的 石头来源 且此行的值始终为1。
在转移矩阵中，A[0,id(i,j)]则代表着i，j这个位置从 石头来源 获取了石头，特别的，A[0,0]应恒为1。
转移矩阵的构造想清楚了就没很大问题了。
Code:
#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define IL inline
#define int long long
#define DB double
using namespace std;
IL int gi() {
RG int x=0,w=0; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') w=1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return w?-x:x;
}
const int N=10;
char op[N],s[N][N];
int n,m,t,cnt,Max,a[N][N],id[N][N];
struct Matrix{
int MT[N*N][N*N];
Matrix operator *(const Matrix &b) {
RG int i,j,k,M=n*m;
RG Matrix c;
for(i=0;i<=M;++i)
for(j=0;j<=M;++j) c.MT[i][j]=0;
for(i=0;i<=M;++i)
for(k=0;k<=M;++k)
for(j=0;j<=M;++j)
c.MT[i][j]+=MT[i][k]*b.MT[k][j];
return c;
}
}f,A[62],PA[62];
IL Matrix qpow(Matrix x,int p) {
RG int i,j;
RG Matrix ans;
for(i=0;i<=n*m;++i)
for(j=0;j<=n*m;++j)
if(i==j) ans.MT[i][j]=1;
else ans.MT[i][j]=0;
for(;p;p>>=1,x=x*x)
if(p&1) ans=ans*x;
return ans;
}
signed main()
{
RG char ss;
RG int i,j,k,p,q,T;
n=gi(),m=gi(),t=gi(),cnt=gi();
for(i=1;i<=n;++i) {
scanf("%s",op);
for(j=1;j<=m;++j)
a[i][j]=(op[j-1]^48),id[i][j]=(i-1)*m+j;
}
for(i=0;i<cnt;++i) scanf("%s",s[i]);
f.MT[0][0]=1;
for(k=1;k<=60;++k) {
A[k].MT[0][0]=1;
for(i=1;i<=n;++i) {
for(j=1;j<=m;++j) {
T=(k-1)%strlen(s[a[i][j]]);
ss=s[a[i][j]][T];
if(ss>='0'&&ss<='9')
A[k].MT[0][id[i][j]]=ss^48,A[k].MT[id[i][j]][id[i][j]]=1;
if(ss=='N'&&i>1) A[k].MT[id[i][j]][id[i-1][j]]=1;
if(ss=='S'&&i<n) A[k].MT[id[i][j]][id[i+1][j]]=1;
if(ss=='W'&&j>1) A[k].MT[id[i][j]][id[i][j-1]]=1;
if(ss=='E'&&j<m) A[k].MT[id[i][j]][id[i][j+1]]=1;
}
}
}
q=t%60,p=(t-q)/60;
for(i=2,PA[1]=A[1];i<=60;++i) PA[i]=PA[i-1]*A[i];
f=f*qpow(PA[60],p)*PA[q];
for(i=1;i<=n*m;++i) Max=max(Max,f.MT[0][i]);
printf("%lld
",Max);
return 0;
}