把每秒石头搬运写成带「外界」注入位的 65×65 矩阵，按序列长度的最小公倍数 ≤60 合成周期矩阵，再用矩阵快速幂把 t ≤ 1e8 秒压到 O(log t)。
OJ: roj
题目 ID: 3090
难度:提高+/省选-
标签:矩阵快速幂周期模拟python
创建: 2026-10-01 16:15
更新: 2026-10-07 13:50
形式化题目
有一个
第
- 字符是数字
：往该格子加入 个石头； - 字符是
N/W/S/E：把该格子内的全部石头推到相邻格子，推出网格外的部分直接消失； - 字符是
D：拿走该格子内的全部石头。
求第
数据范围：
以样例 1 6 10 3、网格 011112、序列 1E / E / 0 为例，把网格摊开可以看出一条传送带：
text
格子 0 1 2 3 4 5
序列 0 1 1 1 1 2
"1E" "E" "E" "E" "E" "0"
用途 每 2 秒 把整格石头收到右边一格 ────▶ 只收不发，
造 1 个 一直累积这条传送带前
| 秒 | 格 0 | 格 1 | 格 2 | 格 3 | 格 4 | 格 5 |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 0 | 0 | 0 | 0 |
| 3 | 1 | 0 | 1 | 0 | 0 | 0 |
| 4 | 0 | 1 | 0 | 1 | 0 | 0 |
| 5 | 1 | 0 | 1 | 0 | 1 | 0 |
| 6 | 0 | 1 | 0 | 1 | 0 | 1 |
| 7 | 1 | 0 | 1 | 0 | 1 | 1 |
| 8 | 0 | 1 | 0 | 1 | 0 | 2 |
| 9 | 1 | 0 | 1 | 0 | 1 | 2 |
| 10 | 0 | 1 | 0 | 1 | 0 | 3 |
观察两件事：格 0 只在偶数秒（第 0，它只加
正解
思路
朴素做法：逐秒模拟。 维护一个
- 数字
：新数组同位置加上 旧值 + d； - 方向：邻居在网格内就加上旧值，否则不加（石头丢弃）；
D：不加任何东西（石头归零）。
这里必须写进新数组而不是原地修改：题面要求所有格子在同一秒内同时动作，如果原地改，先被搬出去的石头会在同一秒里被目标格子再搬一次。
朴素做法的复杂度是
关键观察：每秒的动作用一个矩阵就能完整描述。 再看三种字符：数字是"原地保留 + 加常数"，方向是"整格搬到某处"，D 是"归零"。它们对状态的依赖都是线性的（系数只有
设网格格子数为
三种字符对应的写法是：
| 第 |
含义 | |
|---|---|---|
| 数字 |
原有石头原地保留；外界（恒为 |
|
| 方向，邻居 |
整格石头搬到 |
|
| 方向，越界 | （不写任何项） | 整列为 |
D |
（不写任何项） | 整列为 |
| 外界自身 | 外界恒为 |
用一个 1E，格 1 用序列 0）看具体形状，下标顺序为 [格0, 格1, 外界]：
1：第一列在原地保留的同时向外界列注入 E：第 0 列只有一个
最容易写错的地方：出界石头的处理。它只应让那一列变成全零（石头消失），绝不能写成
周期结构。 第
记
注意顺序：物理上先过完
text
t 秒
├─ 前 q·P 秒：C^q → 矩阵快速幂，约 log2(q) ≤ 27 次矩阵乘法
└─ 余 r 秒：M_{r-1}···M_0 → 最多 59 次「矩阵 × 向量」矩阵规模是
代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 16:18
# update_at: 2026-10-01 16:18
# 每秒钟每个格子的石头都在做「乘 0 或 1 后搬到某格」的线性搬运，t ≤ 1e8 秒没法逐秒模拟，
# 但操作序列每秒循环、整张网格的周期只有 lcm(各序列长度) ≤ 60，于是一整秒就是一次矩阵乘法，
# 用矩阵快速幂把 t 秒压成 O(log t) 次乘法。状态里多留一个「外界」下标：
# 数字 0~9 的加石头 = 外界注入，外界恒为 1，所以每格的注入量是常数；
# 推出网格的石头直接消失，不回流，否则外界会被越喂越多、注入量随秒数指数增长。
import sys
from functools import reduce
from math import lcm
DELTA = {'N': (-1, 0), 'S': (1, 0), 'W': (0, -1), 'E': (0, 1)} # 推石头的四个方向
def mat_mul(a: list[list[int]], b: list[list[int]]) -> list[list[int]]:
"""矩阵乘法 a·b：先把 b 转置成列，再让每个行向量和每个列向量做点积。"""
cols = list(zip(*b))
return [[sum(x * y for x, y in zip(row, col)) for col in cols] for row in a]
def apply(mat: list[list[int]], vec: list[int]) -> list[int]:
"""矩阵乘列向量：算出走一步以后每个下标的石头数。"""
return [sum(a * x for a, x in zip(row, vec)) for row in mat]
def mat_pow(mat: list[list[int]], power: int) -> list[list[int]]:
"""矩阵快速幂 mat^power：把幂按二进制拆成一串平方乘积。"""
size = len(mat)
result = [[int(i == j) for j in range(size)] for i in range(size)]
for bit in range(power.bit_length()):
if power >> bit & 1:
result = mat_mul(result, mat)
mat = mat_mul(mat, mat)
return result
def second_matrix(grid: str, programs: list[str], rows: int, cols: int, second: int) -> list[list[int]]:
"""第 second 秒的转移矩阵：mat[新下标][旧下标] 是旧格子把石头搬给新格子的比例。
数字操作写成「原地留一份 + 外界注入一份」，D 让整列保持 0（石头被拿走），
方向操作把整列搬到相邻格；搬出网格的石头不记进新状态，等于直接丢弃。
"""
outside = rows * cols # 外界：只作为 0~9 加石头的恒定来源，值恒为 1
mat = [[0] * (outside + 1) for _ in range(outside + 1)]
for pos, cell in enumerate(grid):
program = programs[int(cell)]
token = program[second % len(program)]
if token.isdigit():
mat[pos][pos] = 1 # 原有石头原地不动
mat[pos][outside] = int(token) # 外界每格每秒恒定注入这份石头
elif token != 'D':
dr, dc = DELTA[token]
r, c = divmod(pos, cols)
row, col = r + dr, c + dc
if 0 <= row < rows and 0 <= col < cols:
mat[row * cols + col][pos] = 1 # 整格石头搬到相邻格，越界则整列保持 0
mat[outside][outside] = 1 # 外界自保持为 1，注入量才是常数
return mat
def transition_cycle(grid: str, programs: list[str], rows: int, cols: int) -> tuple[list[list[list[int]]], list[list[int]]]:
"""返回 (周期内每秒的转移矩阵, 整周期合成矩阵)：周期长 = 各操作序列长度的最小公倍数。"""
length = lcm(*(len(program) for program in programs))
steps = [second_matrix(grid, programs, rows, cols, second) for second in range(length)]
cycle = reduce(lambda acc, mat: mat_mul(mat, acc), steps) # 先走第 0 秒，后走的乘在左边
return steps, cycle
def solve() -> None:
data = iter(sys.stdin.buffer.read().split())
n, m, t, act = (int(next(data)) for _ in range(4))
grid = ''.join(next(data).decode() for _ in range(n)) # 展平成 rows*cols 一行，方便用下标算坐标
programs = [next(data).decode() for _ in range(act)]
steps, cycle = transition_cycle(grid, programs, n, m)
rounds, rest = divmod(t, len(steps))
vec = [0] * (n * m + 1)
vec[n * m] = 1 # 初始石头全在外界，由它按各格的操作序列注入
for mat in [mat_pow(cycle, rounds), *steps[:rest]]:
vec = apply(mat, vec)
print(max(vec[:n * m])) # 只统计真实格子，外界只是记账
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 18:36
* update_at: 2026-10-06 18:36
*/
// main.cpp：把每秒的搬运动作写成 65×65 矩阵，用周期合成 + 矩阵快速幂解石头游戏。
// 关键点：所有操作序列每秒循环，整周期 P = lcm(各序列长度) ≤ 60；
// 加 0~9 个石头是仿射项，补一个恒为 1 的「外界」分量吸收进矩阵；
// 推出网格的石头直接消失，绝不能回流进外界，否则注入量会指数爆炸。
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 18:35
* update_at: 2026-10-06 18:35
*/
#include <cstdio>
#include <cstring>
typedef long long ll;
const int MAXN = 8; // 网格每边最大 8
const int V = MAXN * MAXN; // 格子数上限 64
const int D = V + 1; // 状态维数：格子 + 外界，最大 65
const int MAXP = 60; // 周期上限：lcm(1..6) = 60
int n, m, act; // 网格规格与操作序列种数
ll t; // 总秒数，最大 1e8
char grid[MAXN][MAXN + 1]; // grid[i][j] = 该格使用的操作序列编号（字符 '0'~'9'）
char prog[10][10]; // prog[k] = 第 k 个操作序列，长度 ≤ 6
int plen[10]; // 每个操作序列的长度
ll period_mat[MAXP][D][D]; // period_mat[s] = 第 s 秒的转移矩阵（mat[新][旧]）
ll cycle_mat[D][D]; // 一个完整周期的合成矩阵 C
ll pow_mat[D][D]; // 矩阵快速幂的工作数组
ll tmp_mat[D][D]; // 矩阵乘法的暂存数组
ll vec[D]; // 当前状态向量（含外界分量）
ll ans_vec[D]; // 乘完矩阵后的结果向量
// 两个方向增量：N 上 / S 下 / W 左 / E 右
int dir_dx(char c) {
if (c == 'N') return -1;
if (c == 'S') return 1;
return 0;
}
int dir_dy(char c) {
if (c == 'W') return -1;
if (c == 'E') return 1;
return 0;
}
// 求 a、b 的最小公倍数
ll gcd_ll(ll a, ll b) {
while (b) {
ll r = a % b;
a = b;
b = r;
}
return a;
}
ll lcm_ll(ll a, ll b) {
return a / gcd_ll(a, b) * b;
}
// 构造第 s 秒的转移矩阵，存进 res：res[新下标][旧下标]
void build_second_matrix(ll res[][D], int s) {
memset(res, 0, sizeof(ll) * D * D);
int outside = n * m; // 外界下标：恒为 1，只作为数字操作的注水源
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int pos = i * m + j;
int k = grid[i][j] - '0';
char c = prog[k][s % plen[k]];
if (c >= '0' && c <= '9') {
res[pos][pos] = 1; // 原有石头原地保留
res[pos][outside] = c - '0'; // 外界每秒恒定注入 d 个
} else if (c != 'D') {
int ni = i + dir_dx(c);
int nj = j + dir_dy(c);
// 整格石头搬到相邻格；越界时不写任何项，整列保持 0，石头消失
if (ni >= 0 && ni < n && nj >= 0 && nj < m)
res[ni * m + nj][pos] = 1;
}
// 'D'：整列保持 0，石头被拿走
}
}
res[outside][outside] = 1; // 外界自保持为 1，注入量才是常数
}
// c = a × b（都是 D×D）
void mat_mul(ll c[][D], ll a[][D], ll b[][D]) {
memset(tmp_mat, 0, sizeof(tmp_mat));
for (int i = 0; i < D; i++)
for (int k = 0; k < D; k++) {
if (a[i][k] == 0) continue; // 稀疏跳零，剪掉大量无效乘法
for (int j = 0; j < D; j++)
tmp_mat[i][j] += a[i][k] * b[k][j];
}
memcpy(c, tmp_mat, sizeof(tmp_mat));
}
int main() {
scanf("%d %d %lld %d", &n, &m, &t, &act);
for (int i = 0; i < n; i++)
scanf("%s", grid[i]);
for (int k = 0; k < act; k++) {
scanf("%s", prog[k]);
plen[k] = strlen(prog[k]);
}
// 整周期 P = 各序列长度的最小公倍数（每个 ≤ 6，所以 P ≤ 60）
int P = 1;
for (int k = 0; k < act; k++)
P = (int)lcm_ll(P, plen[k]);
// 建出周期内每秒的矩阵，并按时间顺序合成整周期矩阵 C = M_{P-1}···M_1 M_0
for (int s = 0; s < P; s++)
build_second_matrix(period_mat[s], s);
for (int i = 0; i < D; i++)
cycle_mat[i][i] = 1; // 单位矩阵作乘法初值
for (int s = 0; s < P; s++)
mat_mul(cycle_mat, period_mat[s], cycle_mat); // 后发生的动作乘在左边
// q = t / P 个整周期用快速幂，余下 r = t % P 秒逐个乘单秒矩阵
ll q = t / P;
int r = (int)(t % P);
for (int i = 0; i < D; i++)
pow_mat[i][i] = 1;
while (q) {
if (q & 1)
mat_mul(pow_mat, pow_mat, cycle_mat);
mat_mul(cycle_mat, cycle_mat, cycle_mat);
q >>= 1;
}
// 初始状态：石头全为 0，只有外界恒为 1
memset(vec, 0, sizeof(vec));
vec[n * m] = 1;
// 物理顺序：先过 q 个整周期（C^q 在右），再过余下 r 秒
for (int i = 0; i < D; i++) {
ans_vec[i] = 0;
for (int j = 0; j < D; j++)
ans_vec[i] += pow_mat[i][j] * vec[j];
}
for (int s = 0; s < r; s++) {
ll nxt[D]; // nxt[新] = M_s × ans_vec
for (int i = 0; i < D; i++) {
nxt[i] = 0;
for (int j = 0; j < D; j++)
nxt[i] += period_mat[s][i][j] * ans_vec[j];
}
for (int i = 0; i < D; i++)
ans_vec[i] = nxt[i];
}
// 只统计真实格子分量，外界只是记账位
ll ans = 0;
for (int i = 0; i < n * m; i++)
if (ans_vec[i] > ans)
ans = ans_vec[i];
printf("%lld\n", ans);
return 0;
}复杂度
记对角线规模的
- 时间：建
个矩阵并合成 需要 ，快速幂 需要 ，合计 ；对比朴素模拟的 ， 时差三个数量级以上。 - 空间：
个整数， 、 时实测峰值内存约 MB。
总结
- 判定正解的信号：动作只依赖时间、不依赖当前状态，且动作是线性的（搬运 / 乘
）+ 常数注入。这时"执行 步"就等价于"求一个矩阵的 次幂"。 - 仿射项（加石头）用齐次坐标处理：补一维恒为
的外界分量，把"加 "变成矩阵的一列。外界必须自封闭，出界石头只能丢弃、不能回流。 - 周期来自"所有序列同时循环"，
；先合成整周期矩阵 ，再对 做快速幂，余下 秒单独乘。 - 矩阵方向约定（
mat[新][旧]）、相乘顺序（后发生的动作乘在左边）是本题实现中最容易出错的细节。