「BZOJ2973」石头游戏

题意：石头游戏在一个 $n$ 行 $m$ 列 $(1≤n,m≤8)$ 的网格上进行，每个格子对应一种操作序列，操作序列至多有 $10$ 种，分别用 $0\sim 9$ 这 $10$ 个数字指明。操作序列是一个长度不超过 $6$ 且循环执行、每秒执行一个字符的字符串。每秒钟，所有格子同时执行各自操作序列里的下一个字符。

序列中的每个字符是以下格式之一：

1. 数字 $0\sim 9$：表示拿 $0\sim9$ 个石头到该格子。
2. $\texttt{NWSE}$：表示把这个格子内所有的石头推到相邻的格子，$\texttt{N}$ 表示上方，$\texttt{W}$ 表示左方，$\texttt{S}$ 表示下方，$\texttt{E}$ 表示右方。
3. $\texttt{D}$：表示拿走这个格子的所有石头。

给定每种操作序列对应的字符串，以及网格中每个格子对应的操作序列，求石头游戏进行了 $t$ 秒之后，石头最多的格子里有多少个石头。在游戏开始时，网格是空的。

解析：一道矩阵乘法的_BZOJ权限题。

设 $\forall i\in [1,n],j \in[1,m],num(i,j)=(i-1)*m+j$。

为了让题目更好做，我们把网格看成一个长度为 $n\times m$ 的一维向量，即定义 $1$ 行 $n\times m+1$ 列的”状态矩阵” $F$，下表为 $0\sim n\times m$，其中 $F[num(i,j)]$ 记录格子 $(i,j)$ 中石头的个数。

特别地，我们要使 $F[0]$ 始终等于 $1$。

这里我们把 $F[0]$ 作为新的石头来源，便于以后与转移矩阵相乘时提供石头。

$F$ 会随着时间增长不断变化。设 $F_k$ 表示 $k$ 秒之后的”状态矩阵”。在游戏开始时，$F_0=[1\ 0\ 0\ ···\ 0]$。

因为操作序列长度不超过 $6$，而 $1\sim6$ 的最小公倍数是 $60$，所以每经过 $60$ 秒，所有操作序列就会回到最开始，即 $60$ 秒为一个周期。我们可以只用统计 $60$ 秒内的状态就够了。

对与 $1\sim60$ 之间的每个 $k$，各个格子在第 $k$ 秒执行的操作字符可以构成一个”转移矩阵” $A_k$，大小为 $(n\times m)\times(n\times m)$。构造方法如下:

1. 如果网格 $(i,j)$ 第 $k$ 秒的操作字符为 $N$，且 $i>1$，就令 $A_k[num(i,j),num(i-1,j)]=1$，表示把石头推到上面去，其他方向的操作类似，注意判断边界。
2. 如果网格 $(i,j)$ 第 $k$ 秒的操作字符为一个数字 $x$，就令 $A_k[0,num(i,j)]=x$，$A_k[num(i,j),num(i,j)]=1$。表示格子从 $F[0]$ 拿 $x$ 颗石头，并且保持原有石头不变。
3. $A_k[0,0]=1$ ，使 $F[0]$ 在转移过程中保持为 $1$。
4. 将 $A_k$ 其余赋值为 $0$。

这四点的正确性证明，手动模拟一下就知道，第一个操作 $F[num(i,j)]\times A_k[num(i,j),num(i-1,j)]=F'[num(i-1,j)]$，通过矩阵乘法的行列变换将石子的数量改到另一列。第二个操作是相当于从第 $0$ 列拿石子，$F[0]$ 为石头来源，第三个操作是为了使 $F[0]$ 一直为 $1$。

最后使用矩阵乘法，使 $ans=\prod_{i=1}^{60}A_i,t=q\times60+r(0\leq r<60)$，即 $F_t=F_0\times ans^q\times \prod_{i=1}^rA_i$。然后再求 $F_t$ 中的最大值即可。

代码：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
long long n,m,t,act,maxx=-1e9;
char a[25][25],b[25][25],len[25];
struct matrix
{
	long long map[71][71];
}x,ans,s[61],now;
matrix multi(matrix a,matrix b)
{
	matrix c=now;
	for(int i=0;i<=n*m;i++)
		for(int j=0;j<=n*m;j++)
			for(int k=0;k<=n*m;k++)
				c.map[i][j]+=a.map[i][k]*b.map[k][j];
	return c;
}
void power(long long b)
{
	for(;b;b>>=1)
	{
		if(b&1)
			ans=multi(ans,x);
		x=multi(x,x);
	}
}
long long num(int i,int j)
{
	return (i-1)*m+j;
}
int main()
{
	scanf("%lld%lld%lld%lld",&n,&m,&t,&act);
	for(int i=1;i<=n;i++)
		scanf("%s",a[i]);
	for(int i=0;i<act;i++)
	{
		scanf("%s",b[i]);
		len[i]=strlen(b[i]);
	}
	for(int i=0;i<=n*m;i++)
		x.map[i][i]=1;
	ans.map[0][0]=1;
	for(int step=0;step<60;step++)
	{
		s[step].map[0][0]=1;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
			{
				int q=a[i][j-1]-'0';
				char r=b[q][step%len[q]];
				if(r>='0'&&r<='9')
				{
					s[step].map[0][num(i,j)]=r-'0';
					s[step].map[num(i,j)][num(i,j)]=1;
				}
				if(r=='N'&&i>1)
					s[step].map[num(i,j)][num(i-1,j)]=1;
				if(r=='S'&&i<n)
					s[step].map[num(i,j)][num(i+1,j)]=1;
				if(r=='E'&&j<m)
					s[step].map[num(i,j)][num(i,j+1)]=1;
				if(r=='W'&&j>1)
					s[step].map[num(i,j)][num(i,j-1)]=1;
			}
		x=multi(x,s[step]);
	}
	power(t/60);
	for(int i=0;i<t%60;i++)
		ans=multi(ans,s[i]);
	for(int i=1;i<=n*m;i++)
		maxx=max(maxx,ans.map[0][i]);
	printf("%lld",maxx);
    return 0;
}