每周五篇博客：（4/5）

https://codeforces.com/contest/2098/problem/D

題意

每個機場都有一個行李索賠區，巴爾貝索沃機場也不例外。在某個時候，Sheremetyevo的一位管理員提出了一個不尋常的想法：將行李索賠傳送帶的傳統形狀從輪播更改為更復雜的形式。

假設行李索賠區域表示為大小 $n\times m$ 的矩形網格。管理局提出，輸送機的路徑應通過 $p_1,p_2,\dots ,p_{2k+1}$ 的單元，其中 $p_i=(x_i,y_i)$ 。

對于每個單元格 $p_i$ 和下一個單元格 $p_{i+1}$ （其中 $1\le i\le 2k$ ），這些單元格必須具有共同的側面。此外，路徑必須很簡單，這意味著對于沒有一對索引 $i\ne j$ ，如果單元格 $p_i$ 和 $p_j$ 的單元格。

不幸的是，路線計劃被溢出的咖啡意外寵壞了，只保留了帶有奇數指數的細胞： $p_1,p_3,p_5,\dots ,p_{2k+1}$ 。您的任務是確定給定這些 $k+1$ 單元格的原始完整路徑 $p_1,p_2,\dots ,p_{2k+1}$ 的方法數量。

由于答案可能很大，因此輸出它模擬 $10^9+7$ 。

思路

首先對于 $p_{2i?1},p_{2i+1}$ ，如果 $|p_{2i?1}?p_{2i+1}|\ne 2$ 的話答案一定是 $0$ ，即我們無法通過兩步的操作從 $p_{2i?1}$ 走到 $p_{2i+1}$

接下來我們進行建圖，如果 $p_{2i?1}$ 與 $p_{2i+1}$ 處于同一行/同一列，那么在他們中間的點連一條自環邊；如果 $p_{2i?1}$ 與 $p_{2i+1}$ 不處于同一行/同一列，那么我們在這兩個點之間可以通過的兩個點進行連邊

例如點 $(1,1),(1,3)$ ，那么我們會在點 $(1,2)$ 處連一條 $(1,2)?(1,2)$ 的無向邊

例如點 $(1,1),(2,2)$ ，那么我們會在點 $(1,2)$ 與 $(2,1)$ 處連一條 $(1,2)?(2,1)$ 的無向邊

連邊本質上是我們讓可以作為 $p_{2i}$ 的點之間連接起來，意思是只要我們選擇邊的某個端點都是合法的一種方案作為鏈接 $p_{2i?1},p_{2i+1}$

連邊后我們會獲得若干個連通塊，而這些連通塊有以下幾種可能：

1. 如果該連通塊的點數比邊數要少，那么答案為 $0$ 。這是因為我們每鏈接一條邊都代表我們需要去選擇一個點去鏈接某對 $p_{2i?1},p_{2i+1}$ 。如果邊比點多的話，那么點數根本就不夠選擇的，所以答案一定是 $0$
2. 如果該連通塊的點數和邊數一樣，表示該連通塊一定存在環，那么同樣分成兩種情況
   1. 該環是某個節點的自環。此時答案根據乘法原理乘以 $1$ 。原因見另一種情況的解釋
   2. 該環包含了超過一個節點的環。此時答案根據乘法原理乘以 $2$ 。這個情況可以參考題目的樣例 $2$ 。如果我們選擇一個點來固定的話，那么其余點的選擇也都固定了。而對于$p_{2i?1},p_{2i+1}$ 中的 $p_{2i}$ 有兩種選擇的可能，所以選擇的點都有兩種方案，那么答案也就是兩種了。同理，對于上一種情況，因為有一個 $p_{2i}$ 點是唯一選擇的，那么答案只能乘以 $1$
3. 如果該連通塊的點數比邊數要多，那么該連通塊一定是棵樹，并且答案根據乘法原理乘以點的數量即可。這是因為我們要選邊的數量的點來作為一種可行的方案，所以在這棵樹中我們可以選擇任意一個點作為無用點后可以得到一個固定的可行方案，而這個無用點的選擇方案有點的數量個

事實上我們也不需要實際建邊再去跑連通分量，只需要用并查集維護每個點都在哪些連通塊即可，具體細節見代碼

代碼

struct DSU {int n;std::vector<int> fa, sz;std::vector<i64> val;explicit DSU(int n): n(n) {fa.assign(n + 1, 0);sz.assign(n + 1, 1);val.assign(n + 1, 0);for (int i = 1; i <= n; i ++) fa[i] = i;}int find(int x) {if (x == fa[x]) return fa[x];int f = fa[x];fa[x] = find(fa[x]);val[x] += val[f];return fa[x];}bool judge(int x, int y) {int dx = find(x), dy = find(y);if (dx == dy) return true;else return false;}void merge(int x, int y, i64 w = 0) {int dx = find(x), dy = find(y);if (dx != dy) {fa[dx] = dy;sz[dy] += sz[dx];val[dx] = -val[x] + val[y] + w;}}
};void solve() {int n, m, k;std::cin >> n >> m >> k;DSU dsu(n * m);std::vector<int> cnt(n * m + 1), loop(n * m + 1);auto get = [&](int x, int y) {return (x - 1) * m + y;};std::vector<PII> a(k + 1);for (int i = 0; i <= k; i ++) std::cin >> a[i].first >> a[i].second;for (int i = 1; i <= k; i ++) {auto [x1, y1] = a[i - 1];auto [x2, y2] = a[i];if (std::abs(x1 - x2) + std::abs(y1 - y2) != 2) {std::cout << "0\n";return ;}int u, v;if (std::abs(x1 - x2) == 1) {u = get(x1, y2), v = get(x2, y1);} else if (x1 == x2) {u = get(x1, (y1 + y2) / 2), v = get(x1, (y1 + y2) / 2);} else if (y1 == y2) {u = get((x1 + x2) / 2, y1), v = get((x1 + x2) / 2, y1);}if (!dsu.judge(u, v)) {cnt[dsu.find(u)] += cnt[dsu.find(v)];loop[dsu.find(u)] |= loop[dsu.find(v)];dsu.merge(v, u);}cnt[dsu.find(u)] ++;if (u == v) loop[dsu.find(u)] = 1;}Z ans = 1;for (int i = 0; i <= n * m; i ++) if (dsu.find(i) == i) {int sz = dsu.sz[i];if (sz < cnt[i]) {ans = 0;break;} else if (sz == cnt[i]) {if (loop[i]) {ans *= 1;} else {ans *= 2;}} else {ans *= sz;}}std::cout << ans << '\n';
}