acwing-206. 石头游戏

发表于 分类于 阅读次数： Waline： 本文字数： 1.3k 阅读时长 ≈ 4 分钟

考点

  • 矩阵乘法
  • 快速幂

题解

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 70;
// 一维向量、60次幂的循环节、转移矩阵
ll f[maxn], sixty[maxn][maxn], A[maxn][maxn][maxn];
// 保存操作序列
string seq[maxn];
int n, m, t, act;
// 每个点对应的操作序列下标
int a[maxn][maxn];
// 每个点当前其操作序列中执行的哪个操作
int state[maxn][maxn];

int num(int i, int j) { return (i - 1) * m + j; }

void mulself(ll a[maxn][maxn], ll b[maxn][maxn]) {
  ll res[maxn][maxn];
  memset(res, 0, sizeof(res));
  for (int i = 0; i <= n * m; ++i)
    for (int j = 0; j <= n * m; ++j)
      for (int k = 0; k <= n * m; ++k) res[i][j] += a[i][k] * b[k][j];
  memcpy(a, res, sizeof(res));
}

void mul(ll a[maxn], ll b[maxn][maxn]) {
  ll res[maxn];
  memset(res, 0, sizeof(res));
  for (int i = 0; i <= n * m; ++i)
    for (int j = 0; j <= n * m; ++j) res[i] += a[j] * b[j][i];
  memcpy(f, res, sizeof(res));
}

// 打表1-60次幂的转移矩阵
void init() {
  for (int k = 1; k <= 60; ++k) {
    A[k][0][0] = 1;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= m; ++j) {
        // 当前执行第x个操作序列的第y个行动
        int x = a[i][j], y = state[i][j];
        char chr = seq[x][y];
        if (isdigit(chr)) {
          A[k][0][num(i, j)] = chr - '0';
          A[k][num(i, j)][num(i, j)] = 1;
        } else if (chr == 'N' && i > 1)
          A[k][num(i, j)][num(i - 1, j)] = 1;
        else if (chr == 'W' && j > 1)
          A[k][num(i, j)][num(i, j - 1)] = 1;
        else if (chr == 'S' && i < n)
          A[k][num(i, j)][num(i + 1, j)] = 1;
        else if (chr == 'E' && j < m)
          A[k][num(i, j)][num(i, j + 1)] = 1;
        state[i][j] = (y + 1) % seq[x].length();
      }
  }
}

int main() {
  cin >> n >> m >> t >> act;
  char chr;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      cin >> chr;
      a[i][j] = chr - '0';
    }
  }
  for (int i = 0; i < act; ++i) cin >> seq[i];
  init();
  memcpy(sixty, A[1], sizeof(A[1]));
  for (int i = 2; i <= 60; ++i) mulself(sixty, A[i]);
  ll ans = 0;
  f[0] = 1;
  int q = t / 60, r = t % 60;
  // 矩阵快速幂
  while (q) {
    if (q & 1) mul(f, sixty);
    mulself(sixty, sixty);
    q >>= 1;
  }
  for (int i = 1; i <= r; ++i) mul(f, A[i]);
  for (int i = 1; i <= n * m; ++i) ans = max(ans, f[i]);
  cout << ans << endl;
  return 0;
}

思路

单看题意其实是纯模拟t次，然而t的范围高达1e9，如果执行线性模拟会超时；

整个题目只有加法操作和乘一个系数操作，考虑矩阵乘法+快速幂加速。

把n * m的网格看作长度为n * m的一维向量，定义1行 (n * m + 1)的状态矩阵F，下标为0 ~ n * m；

已知\(\forall i\in \left[ 1,n \right] ,j\in \left[ 1,m \right]\)，网格原(i, j)的点映射到F的下标为num(i, j) = (i - 1) * m + j，

令F[num(i, j)]记录格子(i, j)中石头的个数，其中F[0] = 1。

设\(F_k\)表示k秒之后的状态矩阵，根据题意，初始时有\(F_0=\left[ \begin{matrix} 1& 0& 0& \cdots& 0\\ \end{matrix} \right]\)，除了0位置之外的所有点石头数均为0。

接下来考虑构造转移矩阵A，矩阵行、列下标都是0 ~ n * m

假设有网格\(\left[ \begin{matrix} a_1& a_2\\ a_3& a_4\\ \end{matrix} \right]\)，转换成状态矩阵变成$F_0=$，其中a0作为新增的常数项位置，恒为1。

假设a1加5，a2、a3、a4均不动，那么有如下等式： \[ \begin{cases} a_1=5\times a_0+1\times a_1+0\times a_2+0\times a_3+0\times a_4\\ a_2=0\times a_0+0\times a_1+1\times a_2+0\times a_3+0\times a_4\\ a_3=0\times a_0+0\times a_1+0\times a_2+1\times a_3+0\times a_4\\ a_4=0\times a_0+0\times a_1+0\times a_2+0\times a_3+1\times a_4\\ \end{cases} \] 这里就体现了常数项a0的作用了，可以很方便地累加；得到转移矩阵如下： \[ \left[ \begin{matrix} 1& 5& 0& 0& 0\\ 0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1\\ \end{matrix} \right] \] 假设a3向上推，其余保持不变，有如下等式： \[ \begin{cases} a_1=0\times a_0+1\times a_1+0\times a_2+1\times a_3+0\times a_4\\ a_2=0\times a_0+0\times a_1+1\times a_2+0\times a_3+0\times a_4\\ a_3=0\times a_0+0\times a_1+0\times a_2+1\times a_3+0\times a_4\\ a_4=0\times a_0+0\times a_1+0\times a_2+0\times a_3+1\times a_4\\ \end{cases} \] 得到转移矩阵如下： \[ \left[ \begin{matrix} 1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 1& 0& 1& 0\\ 0& 0& 0& 0& 1\\ \end{matrix} \right] \]

由于1 - 6之间的数字的最小公倍数是60，意味着最多60次幂的时候，所有的操作序列都会重新回到最开始的1次幂处。

根据快速幂的思路，可以把每60次幂作为一个循环节，预先打表出60次幂得到的转移矩阵sixty；

一共是t次幂，可以拆分成t= q * 60 + r，对于sixty的q次幂，可以直接使用矩阵快速幂进行求解，

而r小于60，直接暴力运算即可。

整理一下最终的转移矩阵构造规律：

  1. 若网格(i, j)第k秒的操作字符为N，且i > 1，那么令A[num(i, j)][num(i - 1, j)] = 1，其余方向类似
  2. 若网格(i, j)第k秒的操作字符是一个数字x，令A[0][num(i, j)] = x，A[num(i, j)][num(i, j)] = 1，表示格子里本来的格子不动，再拿x块石头
  3. 令A[0][0] = 1
  4. 其余部分置0