自动搬运

查看原文

来自洛谷，原作者为

	Liuxizai https://liuxizai.ac.cn | QQ 1684671488

搬运于2025-08-24 22:55:42，当前版本为作者最后更新于2024-02-28 21:31:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Description

给一张 $n\times m$ 的网格，每个格子上有数字 $0\sim 9$ 或 $-1$，其中 $-1$ 表示该格子被封锁。可以在网格上走出一条路径，要求相邻格子四联通，可以经过相同格子，不可以经过被封锁的格子，路径的权值为将格子上的数字按顺序拼成十进制数并对 $P=1145141$ 取模的值。支持两种操作：

1. 修改一个格子上的数。
2. 查询是否存在从 $(sx,sy)$ 到 $(tx,ty)$、权值为 $v$ 的路径。

操作共 $q$ 次。

$1\le n,m\le 500,1\le q\le 2\times 10^5$

Solution

若对网格黑白染色后，同色格上的数字相同，注意这包含了所有格子上的数都相同的情况，我们可以枚举黑白格子上的数字，然后 $O(P)$ 预处理出每个权值是否可达，询问时直接查表即可。也可以使用数学方法。

我们断言，除上述情况之外我们总能找到一组解。

考虑构造证明这一结论。

若「同色格上的数字相同」这一条件不满足，我们总是可以找到四联通的三个格子 $A,B,C$，对应数字分别为 $a,b,c$，满足 $a\ne c$。考虑从起点走到 $B$，然后走若干 $B\to A\to B$ 或 $B\to C\to B$，最后从 $B$ 走到终点。这里前后两段路径带来的权值都是常数，只要证明能在 $A,B,C$ 三个格子上走出任意权值，就证明了整条路径可以取到任何权值。

通过 $B\to A\to B$ 和 $B\to C\to B$ 构成的路径的权值形如 $\overline{b?b?b?b\dots b}$，其中 $?$ 表示 $a$ 或 $c$。令路径长度为 $2\times(P-1)\times(P-1)+1$，所有 $b$ 对权值的贡献是常数，每个 $?$ 的贡献为 $a$ 或 $c$ 乘上位权 $100^k$，其中 $k$ 取 $1\sim(P-1)\times(P-1)$。首先令 $?$ 都为 $a$，此时计算得到一个权值，接下来考虑将若干 $a$ 替换成 $c$，我们要证明这样可以将权值调整至任何数。注意我们有 $100^{P-1}\equiv 1\pmod P$，位权 $100^k$ 中满足 $(P-1)\mid k$ 的 $k$ 共有 $P-1$ 个，仅依靠这些位可以将路径的权值加上不超过 $P-1$ 个 $c-a$，由于 $a\ne c$ 且 $P=1145141$ 是质数，所以 $t(c-a)\bmod P,t\in[0,P-1]\cap\mathbb Z$ 可以取遍 $0\sim P-1$ 中的所有数，于是路径权值可以为任何数。

注意以上证明仅需 $P$ 是质数就可成立，不需要有关 $10$ 或 $10^2=100$ 的任何性质。

于是，对于每次查询，我们只需要判断起点和终点是否在同一个连通块，以及连通块内的同色格上数字是否相同即可。

由于会对格子的封锁状态进行修改，使用线段树分治 + 可撤销并查集维护，复杂度 $O(P+(nm+q)\log q\log nm)$，$P$ 来自预处理。

Code