Solution. LG10201 [湖北省选模拟 2024] 永恒 / eternity
Description
给一张 $n\times m$ 的网格，每个格子上有数字 $0\sim 9$ 或 $-1$，其中 $-1$ 表示该格子被封锁。可以在网格上走出一条路径，要求相邻格子四联通，可以经过相同格子，不可以经过被封锁的格子，路径的权值为将格子上的数字按顺序拼成十进制数并对 $P=1145141$ 取模的值。支持两种操作：
- 修改一个格子上的数。
- 查询是否存在从 $(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
namespace Main{
const int MOD = 1145141;
const int N = 505;
const int Q = 200005;
const vector<pair<int, int>> d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int n, m, q, test_id, mp[N][N], lst[N][N], ans[Q], fa[N * N], num[2][N * N], siz[N * N];
int vis[N][N];
bool col[N * N], ok[10][10][2][MOD + 5];
vector<pair<int*, int>> mem;
void init() { mem = {{nullptr, 0}}; }
void next_version() { mem.emplace_back(nullptr, 0); }
void change(int &x, int y){
mem.emplace_back(&x, x);
x = y;
}
void roll_back(){
while(mem.back().first != nullptr){
*mem.back().first = mem.back().second;
mem.pop_back();
}
mem.pop_back();
}
inline int id(int x, int y) { return (x - 1) * m + y; }
int get(int x){
if(fa[x] == x) return x;
return get(fa[x]);
}
void unite(int x, int y){
x = get(x), y = get(y);
if(x == y) return;
if(siz[x] > siz[y]) swap(x, y);
change(fa[x], y);
change(siz[y], siz[x] + siz[y]);
for(int i: {0, 1}){
if(num[i][x] != -1 && num[i][y] != -1 && num[i][x] != num[i][y]){
change(num[i][y], -2);
}
else if(num[i][x] != -1 && num[i][y] == -1){
change(num[i][y], num[i][x]);
}
}
}
struct segtree{
int st[Q], ed[Q], val[Q];
struct segtree_node{
int l, r;
vector<tuple<int, int, int>> cell;
}t[Q << 2];
#define ls p << 1
#define rs p << 1 | 1
void build(int p, int l, int r){
t[p].l = l, t[p].r = r;
if(l == r) return;
int mid = l + r >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
}
void add(int p, int l, int r, int x, int y, int v){
if(t[p].l >= l && t[p].r <= r){
t[p].cell.emplace_back(x, y, v);
return;
}
int mid = t[p].l + t[p].r >> 1;
if(mid >= l) add(ls, l, r, x, y, v);
if(mid < r) add(rs, l, r, x, y, v);
}
void solve(int p){
if(!t[p].cell.empty()){
next_version();
for(auto [x, y, v]: t[p].cell){
num[col[id(x, y)]][id(x, y)] = v;
change(vis[x][y], 1);
for(auto [dx, dy]: d){
int nx = x + dx, ny = y + dy;
if(vis[nx][ny]) unite(id(x, y), id(nx, ny));
}
}
}
if(t[p].l == t[p].r){
int x = t[p].l;
if(st[x]){
int from = get(st[x]), to = get(ed[x]);
if(from != to) ans[x] = 1;
else if(num[0][from] == -2 || num[1][from] == -2) ans[x] = 2;
else if(num[0][from] == -1 || num[1][from] == -1){
assert(st[x] == ed[x]);
ans[x] = (val[x] == num[0][from] + num[1][from] + 1 ? 2 : 1);
}
else{
int v1 = num[col[st[x]]][from], v2 = num[col[st[x]] ^ 1][from];
if(ok[v1][v2][col[st[x]] == col[ed[x]] ? 1 : 0][val[x]]) ans[x] = 2;
else ans[x] = 1;
}
}
}
else solve(ls), solve(rs);
if(!t[p].cell.empty()) roll_back();
}
#undef ls
#undef rs
}tree;
void Main(){
ios::sync_with_stdio(false), cin.tie(nullptr);
for(int i = 0; i <= 9; i++){
for(int j = 0; j <= 9; j++){
int cur = 0;
for(int k = 1; ; k++){
cur = (cur * 10 + (k & 1 ? i : j)) % MOD;
if(ok[i][j][k & 1][cur]) break;
ok[i][j][k & 1][cur] = true;
}
}
}
cin >> n >> m >> q >> test_id;
for(int i = 1; i <= n; i++){
string s; cin >> s;
for(int j = 1; j <= m; j++){
if(s[j - 1] == '#') mp[i][j] = -1;
else mp[i][j] = s[j - 1] - '0';
}
}
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){
lst[i][j] = 1, col[id(i, j)] = (i + j) & 1;
}
tree.build(1, 1, q);
for(int i = 1; i <= q; i++){
int op; cin >> op;
if(op == 1){
int x, y; char c;
cin >> x >> y >> c;
if(mp[x][y] != -1) tree.add(1, lst[x][y], i - 1, x, y, mp[x][y]);
lst[x][y] = i;
if(c == '#') mp[x][y] = -1;
else mp[x][y] = c - '0';
}
else{
int sx, sy, tx, ty, v;
cin >> sx >> sy >> tx >> ty >> v;
tree.st[i] = id(sx, sy), tree.ed[i] = id(tx, ty);
tree.val[i] = v;
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(mp[i][j] != -1){
tree.add(1, lst[i][j], q, i, j, mp[i][j]);
}
}
}
memset(num, -1, sizeof(num));
for(int i = 1; i <= n * m; i++) fa[i] = i, siz[i] = 1;
tree.solve(1);
for(int i = 1; i <= q; i++) if(ans[i]) cout << (ans[i] == 1 ? "No\n" : "Yes\n");
return;
}
} // namespace Main本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
