题解：B3983 [信息与未来 2024] AI 机器人

沉石鱼惊旋 · 2024-06-06 12:57:06 · 题解

真神啊。不低于省选难度吧？

我们每一步移动的本质，其实是相当于有若干个一样的机器人在很多位置移动，按操作方法移动到了一个位置。最后答案就是这些机器人移动位置的交集。

然而我们发现，对于一个位置 (x_1,y_1)，这上面的机器人所能移动到的位置 (x_2,y_2) 是固定的。因此可以用一个大小为 (n\times m)\times (n\times m) 的 01 矩阵，a_{i,j} 表示编号 i 的点能否到达编号 j 的点。我们这里需要把矩形空间压缩成线性空间，把一个点对映射成一个编号。

我们不妨对于 \tt{U,L,D,R} 每种操作先处理出每种操作，所有位置经过操作时候能到达的位置。这是可以读入了这个矩形空间就能解决的。

接下来我们可以递归（或者用栈处理）这个表达式。

我们简单定义一下以后说到的操作：

矩阵乘法：此处为广义的。我们的矩阵由于维护的是是否可达，所以就是乘法改成做一个 bit_or 运算。也就是 c[i][j] = a[i][k] | b[k][j];。
矩阵加法：还是，广义……？其实表达成矩阵 bit_or 更合适，但是和上文有些重复，还是表述成矩阵加法吧。这里加法也改成 bit_or。也就是 c[i][j] = a[i][j] | b[i][j];。

众所周知，矩阵乘法可以算图上行走 k 步的方案数。类比过来，这里的矩阵乘法可以让我们知道走 k 步能到哪里。而这里的矩阵加法是用来合并路径的。

单次操作是简单的，我们把目前的操作得到的结果和目前这个单次操作做一个矩阵乘法即可。

带有括号不好处理。我们先来讲固定次数怎么做。

在我们已知括号内的操作时，直接循环这么多次，每次用已有操作序列做矩阵乘法，然后路径做一个矩阵加法。

星号同理，但是循环次数不唯一。我们可以发现，其实下面这组测试数据星号需要的循环次数会比较多。

10 10
..........
#########.
#########.
#########.
#########.
#########.
#########.
#########.
#########.
..........
(RD)*

这样的话最坏情况就是 (1,1)\to (1,n)\to(n,m) 得到 18 的长度（第一个点默认走过）。

所以星号跑 18 次，把结果全凑一起就行。

然而还可以构造出要跑更多次的数据，所以这个方法这个方法太菜了。我们可以做到更好的复杂度。

先对目前括号内的操作序列做一个传递闭包，相当于得到了每个点能前往的所有点。然后相当于对这个做一次行走即可。

那么接下来我们求出括号内操作序列即可。对于每个 ( 找到与之匹配的 )，递归搜出这两个中间的操作序列即可。

最后，这题矩阵运算有一个技巧。因为是 01 矩阵，可以用 bitset 优化，这样矩阵乘法复杂度就是 \mathcal O(\frac{n^3}{w}) 的。但是，又发现这题矩阵大小至多 100\times 100，可以用状压的思想把一行压成一个数。这样理论上针对这题的矩阵乘法复杂度就是 \mathcal O(n^2)。可以用 C++ 中的 __int128 储存。

这个方法甚至星号不是瓶颈，有界限的循环才是瓶颈。

时间复杂度 \mathcal O(|s|(nm)^2k)，其中 k=9。可以通过。并且不可能卡满，因此实际效率非常快。

#include <bits/stdc++.h>
using namespace std;
typedef array<__int128, 100> Matrix;
typedef pair<Matrix, Matrix> pMM;
int n, m;
char mp[10][10];
int id[10][10];
__int128 pw[100];
int N;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
inline bool in(int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; }
char to[100];
Matrix base[4];
Matrix ans;
inline void clear(Matrix &x)
{
    for (int i = 0; i < N; i++)
        x[i] = 0;
}
inline void build(Matrix &x)
{
    for (int i = 0; i < N; i++)
        x[i] |= pw[i];
}
Matrix operator|(const Matrix &x, const Matrix &y)
{
    Matrix z;
    clear(z);
    for (int i = 0; i < N; i++)
        z[i] = x[i] | y[i];
    return z;
}
Matrix operator*(const Matrix &x, const Matrix &y)
{
    Matrix z;
    clear(z);
    for (int k = 0; k < N; k++)
        for (int i = 0; i < N; i++)
            if (x[i] >> k & 1)
                z[i] |= y[k];
    return z;
}
Matrix &operator|=(Matrix &x, const Matrix &y) { return x = x | y; }
Matrix &operator*=(Matrix &x, const Matrix &y) { return x = x * y; }
string s;
pMM dfs(int l, int r) // [l, r)
{
    Matrix opt;
    clear(opt);
    build(opt);
    Matrix path;
    clear(path);
    build(path);
    for (int i = l; i < r; i++)
    {
        if (isalpha(s[i]))
        {
            opt *= base[to[s[i]]];
            path |= opt;
            continue;
        }
        int cnt = 0;
        int j = i;
        while (j < r)
        {
            if (s[j] == '(')
                cnt++;
            if (s[j] == ')')
                cnt--;
            j++;
            if (!cnt)
                break;
        }
        auto [op, mp] = dfs(i + 1, j - 1);
        if (s[j] == '*')
        {
            build(op);
            for (int x = 0; x < N; x++)
                for (int y = 0; y < N; y++)
                    if (op[x] >> y & 1)
                        op[x] |= op[y];
            path |= opt * op * mp;
            opt *= op;
        }
        else
        {
            for (int k = 0; k < (s[j] ^ '0'); k++)
            {
                path |= opt * mp;
                opt *= op;
            }
        }
        i = j;
    }
    return {opt, path};
}
int main()
{
    to['R'] = 0, to['L'] = 1, to['D'] = 2, to['U'] = 3;
    pw[0] = 1;
    for (int i = 1; i < 100; i++)
        pw[i] = pw[i - 1] << 1;
    cin >> n >> m;
    N = n * m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> mp[i][j];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            id[i][j] = i * m + j;
    for (int i = 0; i < 4; i++)
    {
        for (int x = 0; x < n; x++)
        {
            for (int y = 0; y < m; y++)
            {
                int tx = x + dx[i];
                int ty = y + dy[i];
                base[i][id[x][y]] |= pw[in(tx, ty) && mp[tx][ty] == '.' ? id[tx][ty] : id[x][y]];
            }
        }
    }
    cin >> s;
    ans = dfs(0, s.size()).second;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (mp[i][j] == '#')
                putchar('#');
            else if (ans[0] >> id[i][j] & 1)
                putchar('+');
            else
                putchar('.');
        }
        putchar('\n');
    }
    return 0;
}