Solution. LG10201 [湖北省选模拟 2024] 永恒 / eternity

· · 题解

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