不是最小生成树计数.

Description

在地面上有一个水箱, 它的俯视图被划分成了$n$行$m$列个方格, 相邻两个方格之间有一堵厚度可以忽略不计的墙, 水

箱与外界之间有一堵高度无穷大的墙, 因此水不可能漏到外面. 已知水箱内每个格子的高度都是$[0,H]$之间的整数

, 请统计有多少可能的水位情况. 因为答案可能很大, 请对$10^9+7$取模输出. 两个情况不同当且仅当存在至少一个

方格的水位在两个情况中不同.

Solution

考虑最小生成树的过程, 两个位置在一个联通块内意味着他们的高度相同. 则在联通前的答案相乘后可贡献到新的根上, 此后作为一个整体参与贡献. 注意在合并前累加当前边和集合高度的差.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
#define mod 1000000007

using namespace std;

const int maxn = 500005;

struct edge {
  int frm, to, v;
  inline bool operator<(const edge &rhs) const {
    return v < rhs.v;
  }
}e[maxn << 1];
int n, m, h, ptr, sz, res;
int f[maxn], mx[maxn], ans[maxn];

inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}
inline int getid(int x, int y) {
  return (x - 1) * m + y;
}
inline void add(int bgn, int end, int val) {
  e[++ptr] = (edge){bgn, end, val};
}
int find(int x) {
  return f[x] == x ? x : f[x] = find(f[x]);
}
inline void link(int x, int y, int val) {
  int fx = find(x), fy = find(y);
  if (fx != fy) {
    f[fx] = fy;
    ans[fx] = (ans[fx] + val - mx[fx]) % mod;
    ans[fy] = (ans[fy] + val - mx[fy]) % mod;
    ans[fy] = 1ll * ans[fx] * ans[fy] % mod;
    mx[fy] = val;
  }
}

int main() {
  n = rd(); m = rd(); h = rd();
  for (int i = 1; i <= n * m; ++i) 
    f[i] = i, mx[i] = -1;
  int v;
  for (int i = 1; i <= n; ++i) {
    for (int j = 2; j <= m; ++j) {
      v = rd();
      add(getid(i, j - 1), getid(i, j), v);
    }
  }
  for (int i = 2; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      v = rd();
      add(getid(i - 1, j), getid(i, j), v);
    }
  }
  sort(e + 1, e + 1 + ptr);
  sz = n * m; res = 1;
  for (int i = 1, j = 1; i <= ptr; ++i) {
    link(e[i].frm, e[i].to, e[i].v);
  }
  for (int i = 1; i <= n * m; ++i)
    if (find(i) == i) {
      res = 1ll * res * (ans[i] + h - mx[i]) % mod;
    }
  printf("%d\n", res);
  return 0;
}