bzoj 2973
题意：见上。
我们考虑一维怎么做，其实二维就可以在一维基础上标号即可。
然后对于原题就是一个矩阵转化的过程。根据$T$很大也可以看出。
操作序列不一样长可以求个$lcm$然后都等长，因为$lcm(1,2,…,6)=60$，所以不会很大
根据转移矩阵构造方法：若状态矩阵中的第 $x$ 个数对下个单位时间状态矩阵的第 $y$ 个数产生影响，则吧转移矩阵的第 $x$ 行第$ y$ 列赋值为适当的系数
对于方向的移动，我们让$(x,y)->(x+dx,y+dy)=1$
对于数字的增加，我们让$(0,y)->(x,y)=x, (x,y)->(x,y)=1$
此时我们就要保证$(0, 0)->(0, 0)=1$，否则转移就没了
对于D，不用额外操作。
然后矩阵快速幂求$lcm$的整块即可。不完整的块暴力。
知识点：
1、根据转移矩阵构造方法：若状态矩阵中的第 $x$ 个数对下个单位时间状态矩阵的第 $y$ 个数产生影响，则吧转移矩阵的第 $x$ 行第$ y$ 列赋值为适当的系数
2、矩阵乘法不要写错，快速幂$BS$自乘不要写错
3、判==0不要忘了写
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
struct matrix {
LL x, y, a[100][100];
void init(LL n, LL m) {x = n, y = m, ms(a, 0ll);}
}A[65], tt, f;
LL l, n, m, t, act, len[10];
char s[10][10], opt[10][10];
LL gcd(LL a, LL b) {return b == 0ll ? a : gcd(b, a % b);}
LL lcm(LL a, LL b) {return a * b / gcd(a, b);}
LL getIDByPos(LL x, LL y) {return (x - 1ll) * m + y;}
matrix mul(matrix a, matrix b) {
matrix ret; ret.init(a.x, b.y);
for (LL i = 0ll; i <= a.x; ++i) {
for (LL j = 0ll; j <= a.y; ++j) {
for (LL k = 0ll; k <= b.x; ++k) ret.a[i][j] += a.a[i][k] * b.a[k][j];
}
}
return ret;
}
matrix ksm(matrix a, LL b) {
matrix bs = a, ans;
int fl = 0ll;
while (b) {
if (b & 1ll) {
if (!fl) fl = 1ll, ans = bs; else ans = mul(ans, bs);
}
bs = mul(bs, bs);
b >>= 1ll;
}
return ans;
}
void clean() {
}
int solve() {
clean();
l = 1ll;
cin >> n >> m >> t >> act;
for (LL i = 1ll; i <= n; ++i) scanf("%s", s[i] + 1ll);
for (LL i = 0ll; i < act; ++i) scanf("%s", opt[i]), len[i] = strlen(opt[i]), l = lcm(l, len[i]);
tt.init(n * m, n * m);
for (LL i = 0; i <= n * m; ++i) tt.a[i][i] = 1ll;
for (LL i = 0ll; i < l; ++i) {
A[i].init(n * m, n * m), A[i].a[0][0] = 1ll;
for (LL x = 1ll; x <= n; ++x) {
for (LL y = 1ll; y <= m; ++y) {
char op = opt[s[x][y] - '0'][i % len[s[x][y] - '0']];
if (op == 'N' && x - 1ll > 0ll) A[i].a[getIDByPos(x, y)][getIDByPos(x - 1ll, y)] = 1ll;
if (op == 'S' && x + 1ll <= n) A[i].a[getIDByPos(x, y)][getIDByPos(x + 1ll, y)] = 1ll;
if (op == 'E' && y + 1ll <= m) A[i].a[getIDByPos(x, y)][getIDByPos(x, y + 1ll)] = 1ll;
if (op == 'W' && y - 1ll > 0ll) A[i].a[getIDByPos(x, y)][getIDByPos(x, y - 1ll)] = 1ll;
if ('0' <= op && op <= '9') A[i].a[0][getIDByPos(x, y)] = op - '0', A[i].a[getIDByPos(x, y)][getIDByPos(x, y)] = 1ll;
}
}
tt = mul(tt, A[i]);
}
tt = ksm(tt, t / l);
for (LL i = 0ll; i < t % l; ++i) tt = mul(tt, A[i]);
f.init(1ll, m * n), f.a[0][0] = 1ll;
f = mul(f, tt);
LL maxd = 0;
for (LL i = 1ll; i <= n * m; ++i) maxd = max(maxd, f.a[0][i]);
cout << maxd;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
描述
石头游戏在一个 n 行 m 列 (1≤n,m≤8) 的网格上进行，每个格子对应一种操作序列，操作序列至多有10种，分别用0~9这10个数字指明。
操作序列是一个长度不超过6且循环执行、每秒执行一个字符的字符串。每秒钟，所有格子同时执行各自操作序列里的下一个字符。序列中的每个字符是以下格式之一：
数字0~9：表示拿0~9个石头到该格子。
NWSE：表示把这个格子内所有的石头推到相邻的格子，N表示上方，W表示左方，S表示下方，E表示右方。
D：表示拿走这个格子的所有石头。
给定每种操作序列对应的字符串，以及网格中每个格子对应的操作序列，求石头游戏进行了 t 秒之后，石头最多的格子里有多少个石头。在游戏开始时，网格是空的。
输入格式
第一行4个整数n, m, t, act。
接下来n行，每行m个字符，表示每个格子对应的操作序列。
最后act行，每行一个字符串，表示从0开始的每个操作序列。
输出格式
一个整数：游戏进行了t秒之后，所有方格中最多的格子有多少个石头。
样例输入
1 6 10 3
011112
1E
E
0
样例输出
3
样例解释
这是另一个类似于传送带的结构。左边的设备0间隔地产生石头并向东传送。设备1向右传送，直到设备2。10秒后，总共产生了5个石头，2个在传送带上，3个在最右边。
