奇怪的联通性 DP...

一句话题意:给定网格图,求满足物理原理的空白部分填充方案数。

行数列数 $n,m\le 1000$。

这里的物理原理大概包括两条:重力作用原理和连通器原理好像是一个东西

一个原始的想法是从下向上 DP。

但是方格之间有支配关系。考虑以下一个例子:

#####
#...#
#.#.#
#...#
#####

答案为 $4$,显然观察得到上层的方格一定支配下层方格,一共 $3$ 层。

但是我们从此得知,两个方格的是否关联要基于 $2$ 个因素:

  1. 在一个联通块中;
  2. 支配者层数相同或高于被支配的方格。

所以我们考虑从下向上维护并查集。

状态的转移在这里却是比较平凡的。

对于一个方格 $(x,y)$ 代表的在 $x$ 层及以下的连通块中,若干可以联通且层数多 $1$ 的联通块代表元素的集合为 $S$。

注意, $S$ 中元素在 $x$ 层上是联通的,但是在 $x+1$ 层上是不联通的。

有:

$$ f_{x,y} = 1+\prod_{(i,j)\in S}f_{i,j} $$

因为如果 $(x,y)$ 充水,就只有一种情况,否则 $S$ 中块互不干扰。

所以有了 $\mathcal O(nm)$ 次并查集 find 操作复杂度的解法。

具体实现中:

从下到上枚举每一行 $x$。

首先存下 $x+1$ 的所有点在并查集中的父亲。(代表下文「合并前的并查集」。)

然后对于 $x$ 行的空点,合并与其连通的所有点。(即「合并后的并查集」。)

再枚举 $x+1$ 行所有空点,如果它在合并后的并查集中的祖先在 $x$ 行,则说明它对目前答案有贡献,用它在合并前的并查集中的祖先更新合并后的并查集的祖先。

注意这里每个合并前的祖先只能贡献一次。

然后对 $x$ 行所有点 $f$ 值 $+1$。

这里有并查集合并前与合并后之分,是难理解的地方。

最后答案是所有连通块的答案之积。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>

const int N = 1001;
const int NODE = N * N;
const int p = 1000000007;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); }
    do x = x * 10 + ch - 48, ch = getchar(); while(ch >= '0' && ch <= '9');
    return x * f;
}
inline int readchar() {
    char ch = getchar();
    while(ch != '#' && ch != '.') ch = getchar();
    return ch;
}

int n,m; char map[N][N];
struct Point {
    int x,y;
    Point() {}
    Point(int _x,int _y): x(_x), y(_y) {}
    friend bool operator ==(const Point &x,const Point &y) {
        return x.x == y.x && x.y == y.y;
    }
};
Point fa[N][N]; int fa1[N];
int vis[N][N],f[N][N];
Point find(Point x) {
    if(fa[x.x][x.y] == x) return x;
    return fa[x.x][x.y] = find(fa[x.x][x.y]);
}
int find1(int x) {
    if(fa1[x] == x) return x;
    return fa1[x] = find1(fa1[x]);
}
void Join(Point x,Point y) {
    x = find(x), y = find(y);
    fa[y.x][y.y] = x;
}

int main() {
    n = read(), m = read();
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++) {
            map[i][j] = readchar();
            fa[i][j] = Point(i,j);
        }
    for(int i = n - 1;i >= 1;i--) {
        for(int j = 1;j <= m;j++) fa1[j] = fa[i + 1][j].y, vis[0][j] = false;
        for(int j = 1;j <= m;j++) if(map[i][j] == '.') {
            f[i][j] = 1;
            if(map[i + 1][j] == '.') Join(Point(i,j),Point(i + 1,j));
            if(map[i][j - 1] == '.') Join(Point(i,j),Point(i,j - 1));
            if(map[i][j + 1] == '.') Join(Point(i,j),Point(i,j + 1));
        }
        for(int j = 1;j <= m;j++) if(map[i + 1][j] == '.') {
            Point F = find(Point(i + 1,j));
            if(F.x != i) continue;
            int F1 = find1(j);
            if(vis[0][F1]) continue;
            vis[0][F1] = true;
            f[i][F.y] = 1ll * f[i][F.y] * f[i + 1][F1] % p;
        }
        for(int j = 1;j <= m;j++) if(map[i][j] == '.') f[i][j]++;
        // for(int i = 1;i <= n;i++, std::puts(""))
        //  for(int j = 1;j <= m;j++) std::printf("%d ",f[find(Point(i,j)).x][find(Point(i,j)).y]);
        // std::puts("");
    }
    int ans = 1;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++) if(map[i][j] == '.') {
            Point F = find(Point(i,j));
            if(vis[F.x][F.y]) continue;
            vis[F.x][F.y] = true;
            ans = 1ll * ans * f[F.x][F.y] % p;
        }
    std::printf("%d ",ans);
    return 0;
}