题解：CF2247F Paths on a Grid

· · 题解

分析

考虑什么情况下经过 (a,b) 的路径必然经过 (c,d)；经过 (c,d) 的路径必然经过 (a,b)。

显然，要求是经过 (a,b) 的路径集合等于经过 (c,d) 的路径集合。

对每个格子随机权值 val。对于一个格子 (a,b)，记 cnt(c,d) 为所有经过 (a,b) 的路径中，经过 (c,d) 的路径数量。维护 H_{p}(a,b) = \sum\limits_{c=1}^{n}\sum\limits_{d=1}^{m}(cnt(c,d)\cdot val(c,d))\bmod p。

拆成两部分，一部分是 (1,1) 到 (a,b) 的；一部分是 (a,b) 到 (n,m) 的。维护 f_{0/1,p}(a,b) 和 g_{0/1,p}(a,b)。分别表示两部分的价值和，方案数。

以 f_{0,p},g_{0,p} 举例，有：

  1. 若 (a-1,b) 是自由的，且 (a,b) 是自由的，则 f_{0,p}(a,b)\gets f_{0,p}(a-1,b),g_{0,p}(a,b)\gets g_{0,p}(a-1,b)。(a,b-1) 同理。
  2. 若 (a,b) 是自由的，f_{0,p}(a,b)\gets g_{0,p}(a,b)\cdot val(a,b)。

最后 H_p(a,b) = (f_{0,p}(a,b)\cdot g_{1,p}(a,b) + f_{1,p}(a,b)\cdot g_{0,p}(a,b)-val(a,b)\cdot g_{0,p}(a,b)\cdot g_{1,p}(a,b))\bmod p。

取一个模数集合 C。那么 (a,b) 和 (c,d) 可以同时选择的必要条件就是 \forall p\in C, H_{p}(a,b) = H_{p}(c,d)。

时间复杂度 O(nm|C|+nm\log V)。

代码

#define id(x, y) ((x - 1) * m + (y))

const int N = 1e6 + 10, M = 4, mod = 998244353;
int Mod[] = {1000000663, 1000000801, 900000053, 700000069};
vector<char> vec;
vector<int> val;
vector<int> f[2][M];
vector<int> g[2][M];
int n, m;
map<int, int> mp;

il void solve(){ 
    mp.clear();
    n = rd, m = rd;
    vec.resize((n + 1) * (m + 1));
    val.resize((n + 1) * (m + 1));
    U(c, 0, 1) U(x, 0, 3) f[c][x].resize((n + 1) * (m + 1)), g[c][x].resize((n + 1) * (m + 1));
    U(i, 1, n){
        U(j, 1, m){
            cin >> vec[id(i, j)];
            val[id(i, j)] = rnd() % 100000000 + 1;
        }
        U(c, 0, 1) U(x, 0, 3){
            U(j, 1, m) f[c][x][id(i, j)] = g[c][x][id(i, j)] = 0;
        }
    }
    U(x, 0, 3){
        f[0][x][id(1, 1)] = val[id(1, 1)] % Mod[x];
        g[0][x][id(1, 1)] = 1;
        U(i, 1, n) U(j, 1, m) if(vec[id(i, j)] == '1' && (i + j)){
            if(i - 1 >= 1 && vec[id(i - 1, j)] == '1'){
                f[0][x][id(i,j)] = (f[0][x][id(i,j)] + f[0][x][id(i - 1,j)]) % Mod[x];
                g[0][x][id(i,j)] = (g[0][x][id(i,j)] + g[0][x][id(i - 1,j)]) % Mod[x];
            }
            if(j - 1 >= 1 && vec[id(i, j - 1)] == '1'){
                f[0][x][id(i,j)] = (f[0][x][id(i,j)] + f[0][x][id(i,j - 1)]) % Mod[x];
                g[0][x][id(i,j)] = (g[0][x][id(i,j)] + g[0][x][id(i,j - 1)]) % Mod[x];
            }
            f[0][x][id(i,j)] = (f[0][x][id(i,j)] + val[id(i, j)] * g[0][x][id(i,j)]) % Mod[x];
        }

        f[1][x][id(n,m)] = val[id(n,m)] % Mod[x];
        g[1][x][id(n,m)] = 1;
        D(i, n, 1) D(j, m, 1) if(vec[id(i, j)] == '1' && (i + j != n + m)){
            if(i + 1 <= n && vec[id(i + 1, j)] == '1'){
                f[1][x][id(i,j)] = (f[1][x][id(i,j)] + f[1][x][id(i + 1,j)]) % Mod[x];
                g[1][x][id(i,j)] = (g[1][x][id(i,j)] + g[1][x][id(i + 1,j)]) % Mod[x];
            }
            if(j + 1 <= m && vec[id(i, j + 1)] == '1'){
                f[1][x][id(i,j)] = (f[1][x][id(i,j)] + f[1][x][id(i,j + 1)]) % Mod[x];
                g[1][x][id(i,j)] = (g[1][x][id(i,j)] + g[1][x][id(i,j + 1)]) % Mod[x];
            }
            f[1][x][id(i,j)] = (f[1][x][id(i,j)] + val[id(i, j)] * g[1][x][id(i,j)]) % Mod[x];
        }
    }
    U(i, 1, n) U(j, 1, m){
        int V = 1;
        U(x, 0, 3){
            int v = (f[0][x][id(i,j)] * g[1][x][id(i,j)] + f[1][x][id(i,j)] * g[0][x][id(i,j)]) % Mod[x];
            v = (v - val[id(i, j)] * g[0][x][id(i,j)] % Mod[x] * g[1][x][id(i,j)] % Mod[x] + Mod[x]) % Mod[x];
            V *= (v + 1);
        }
        ++ mp[V];
    }
    int res = 0;
    for(auto [x, y]: mp) res = (res + qmi(2, y, mod) - 1 + mod) % mod;
    cout << res << "\n";
    return ;
}