「THUPC 2026 初赛」覆盖游戏

0
admin LV 10 SU @ 2026-4-23 20:14:32
写在前面

出题人题解，场上一共有 0 个队伍做出此题。

感谢验题人 rsy 指出了本题有线性做法并且为题解换上了更好看的图片。

正解过程

在本篇题解中，我们将红色矩形称为横长条，蓝色矩形称为纵长条。

考虑一种覆盖。我们先定义一个名词：指向。对一个横长条，我们称它指向它所在行的黑格；对一个纵长条，我们称它指向它所在列的黑格。

我们再在每个白格摆上箭头，如果此白格被横长条覆盖则摆上 $\leftrightarrow$ ，被纵长条覆盖则摆上 $\updownarrow$ 。

我们先证明一个引理：

为了满足“你需要用手上的长条互不重叠地覆盖所有白格，同时你不能覆盖到黑格”，至少需要用到 $2n-2$ 个长条。

证明的主题思想是考虑每个黑格被多少个长条指向。
- Case 1：存在一个黑格没有被任何长条指向。
如上图，与此黑格同行同列的白格所摆上的箭头都已经确定，并且对应的长条互不相同，所以至少有 $2n-2$ 个长条。
- Case 2：每个黑格都至少被一个长条指向，且有两个黑格均只被一个长条指向（不要求是同一个长条）。
如上图，假设两个黑格均只被一个长条指向，考虑这两个黑格所架出的两个十字架内的所有白格。首先看其中一个与两个黑格均同行/同列的白格，比如说右上方红色的那一格，不妨设它的箭头是 $\color{red}\leftrightarrow$ ，那么左下方蓝色那一格的箭头只能是 $\color{blue}\leftrightarrow$ ，与此同时图中标出的箭头都是可以完全确定的。（这里的红色箭头和蓝色箭头与题面中红色矩形和蓝色矩形的定义无关）

设这两个黑格中间有 $u$ 列，现在数至少需要的长条数。纵长条至少需要 $n - 2 - u$ 个，横长条忽略中间 $u$ 列的黑格的话至少要 $n$ 个，而中间这 $u$ 列对应 $u$ 个黑格会使得原本可能贯通中间 $u$ 列的横长条分开。所以至少再多 $u$ 个横长条。一共至少需要 $n - 2 - u + n + u = 2n-2$ 个长条。
- Case 3：每个黑格都至少被一个长条指向，且至多一个黑格只被一个长条指向（即其他黑格都至少被两个长条指向）
注意到每个长条恰指向一个黑格，则简单的算两次可以知道至少要 $2n-1$ 个长条。

引理得证，下面回到原题。

由于题目要求用 $2n-2$ 个长条覆盖，恰好是最小需求量，所以我们只需要考虑 Case 1 和 Case 2 中取等时有多少种方案就行，也就是要求出现的所有长条都是用已标记的 $\leftrightarrow$ 和 $\updownarrow$ 延申来得到。

从 Case 1 中很明显可以看到，我们可以把方案数分成四部分去求，即左上，左下，右上，右下四个待填充区域，然后把四部分的方案数相乘即可，同时对于 Case 2，中间 $u$ 列已经不需要考虑，直接让横长条延申覆盖满即可，然后两边的又可以化归为左下，右下，左上，右上四部分的方案数相乘，所以只需要考虑对于一个黑格及其左上/左下/右上/右下部分的方案数。

（但是 Case 2 中那个红色的箭头也可能是 $\color{red}{\updownarrow}$ ，也要统计这部分的方案数）

我们不妨考虑右上的部分。首先，注意到如果有两个黑格长成“左上到右下”的样子（如下图中红格），那么就有一个白格（图中画 $\color{red}\times$ 的格）无法通过已标记的黑格延申得到，就不能做到 $2n-2$ 格长条覆盖。

所以这部分的黑格必须是呈现“左下到右上”的趋势的，也就是说，对这一局部图中任意坐标的两个黑格 $(i_1, j_1)$ ， $(i_2, j_2)$ ，倘若 $i_1 > i_2$ ，则必有 $j_1 < j_2$ ，其中 $(1, 1)$ 为整个 $n\times n$ 方格表最左上角的格子。

判断是否有这种趋势是简单的，用一个 set 从右往左扫，维护对应行的前驱就行，因为“是否满足这个趋势”可从前驱传递过来。

现在假设黑格确实满足了“左下到右上”的趋势。我们随便画一个满足要求的覆盖，然后考虑横长条和纵长条公共边界的部分，恰好连成了一个从左下到右上的路径，此路径碰到了所有黑格，然后每一步只能往上或往右走（见下图红线）。同样地，一种碰到所有黑格的，从左下到右上的，每步往上或往右的路径可以对应到一种延申方式。

需要注意的是，这并不是一一对应的，因为如果你走到了一个黑格的左下角，那么走到右上角的两种方式在长条延申意义下相当于一种了。不过统计这个方案数有很强的递推关系，所以我们只需要考虑两个黑格的情况即可。

如下图，假设需要从点 $O$ 出发走到右上角，那么走到终点的前一步可能是到 $A$ 和 $B$ ，但是 $C \rightarrow A$ 和 $C \rightarrow B$ 是一样的，所以还要减去从 $O$ 到 $C$ 的方案数。

综上，对于这一个局部，长条延申的方案数为
$O\ 到\ A\ 方案数 + O\ 到\ B\ 方案数 - O\ 到\ C\ 方案数$
每一小部分都是一个形如 $\binom{行 + 列}{行}$ 的组合数，可以预处理，然后对一个有“左下到右上”趋势的黑格团，直接把在“左下到右上”意义下相邻的黑格之间的方案数求出来，最后全部相乘即可。这部分统计可以和用 set 维护前驱时一并维护起来。

最后求总方案数是简单的，维护一下前缀和然后直接求就行。

时间复杂度为 $O(n \log n)$ 。事实上可以非常简单地通过双向链表或单调栈把维护前驱的过程线性，达到 $O(n)$ 的复杂度。
```
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
using namespace std;
#define ll long long
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define per(i, x, y) for(int i = x; i >= y; --i)
inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
    return x * f;
}
const int N = 200010, mod = 1000000007;
int n, a[N], fac[N], inv[N], minn, val[N][4], idx[N], pre[N][4], A[N], B[N], C_[N], D[N], E[N];
inline int fpow(int x, int p){
	int ans = 1;
	for(; p; p >>= 1, x = 1ll * x * x % mod) if(p & 1) ans = 1ll * ans * x % mod;
	return ans;
}
inline void initfac(int n){
	fac[0] = 1; rep(i, 1, n) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[n] = fpow(fac[n], mod - 2);
	per(i, n - 1, 0) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}
inline int C(int n, int m){
	if(n < 0 || m < 0 || n < m) return 0;
	return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
} 
struct node{ int x, y; node(int a = 0, int b = 0){ x = a, y = b; } };
struct block{ int x, y; node zs, ys, zx, yx; }c[N], d[N];
inline bool cmp(block x, block y){ return x.x < y.x; }
set <int> st0, st1, st2, st3; set <int> :: iterator it;
inline int walk(node x, node y){ return C(abs(x.x - y.x) + abs(x.y - y.y), abs(x.x - y.x)); }
inline int calc(block a, block b, int id){
	if(id == 0) return ((walk(a.zs, b.zs) - walk(a.yx, b.zs)) % mod + mod) % mod;
	if(id == 1) return ((walk(a.ys, b.ys) - walk(a.zx, b.ys)) % mod + mod) % mod;
	if(id == 2) return ((walk(a.zx, b.zx) - walk(a.ys, b.zx)) % mod + mod) % mod;
	if(id == 3) return ((walk(a.yx, b.yx) - walk(a.zs, b.yx)) % mod + mod) % mod; 
}
inline void mian(){
    n = read(); initfac(n);
	rep(i, 1, n){
		c[i].y = i; c[i].x = a[i] = read();
		idx[c[i].x] = i;
		c[i].zs = node(c[i].x - 1, c[i].y - 1);
		c[i].ys = node(c[i].x - 1, c[i].y);
		c[i].zx = node(c[i].x, c[i].y - 1);
		c[i].yx = node(c[i].x, c[i].y);
		d[i] = c[i];
	}
	minn = n + 1; st0.insert(0); st0.insert(n + 1);
	rep(i, 1, n){
		if(d[i].x > minn){
			pre[d[i].y][0] = -1;
			st0.insert(d[i].x);
			continue;
		}
		it = st0.lower_bound(d[i].x);
		int u = *it, v = *(--it);
		if(v == 0){
			val[d[i].y][0] = walk(node(0, 0), d[i].zs);
			pre[d[i].y][0] = 0;
		}
		else{
			val[d[i].y][0] = calc(d[idx[v]], d[i], 0);
			pre[d[i].y][0] = idx[v];
		}
		minn = min(minn, u); st0.insert(d[i].x);
	}
	minn = n + 1; st1.insert(0); st1.insert(n + 1);
	per(i, n, 1){
		if(d[i].x > minn){
			pre[d[i].y][1] = -1;
			st1.insert(d[i].x);
			continue;
		}
		it = st1.lower_bound(d[i].x);
		int u = *it, v = *(--it);
		if(v == 0){
			val[d[i].y][1] = walk(node(0, n), d[i].ys);
			pre[d[i].y][1] = n + 1;
		}
		else{
			val[d[i].y][1] = calc(d[idx[v]], d[i], 1);
			pre[d[i].y][1] = idx[v];
		}
		minn = min(minn, u); st1.insert(d[i].x);
	}
	minn = 0; st2.insert(0); st2.insert(n + 1);
	rep(i, 1, n){
		if(d[i].x < minn){
			pre[d[i].y][2] = -1;
			st2.insert(d[i].x);
			continue;
		}
		it = st2.lower_bound(d[i].x);
		int u = *it, v = *(--it);
		if(u == n + 1){
			val[d[i].y][2] = walk(node(n, 0), d[i].zx);
			pre[d[i].y][2] = 0;
		}
		else{
			val[d[i].y][2] = calc(d[idx[u]], d[i], 2);
			pre[d[i].y][2] = idx[u];
		}
		minn = max(minn, v); st2.insert(d[i].x);
	}
	minn = 0; st3.insert(0); st3.insert(n + 1);
	per(i, n, 1){
		if(d[i].x < minn){
			pre[d[i].y][3] = -1;
			st3.insert(d[i].x);
			continue;
		}
		it = st3.lower_bound(d[i].x);
		int u = *it, v = *(--it);
		if(u == n + 1){
			val[d[i].y][3] = walk(node(n, n), d[i].yx);
			pre[d[i].y][3] = n + 1;
		}
		else{
			val[d[i].y][3] = calc(d[idx[u]], d[i], 3);
			pre[d[i].y][3] = idx[u];
		}
		minn = max(minn, v); st3.insert(d[i].x);
	}
	val[0][0] = val[0][2] = val[n + 1][1] = val[n + 1][3] = 1;
	rep(i, 1, n){
		if(pre[i][0] == -1) continue;
		val[i][0] = 1ll * val[i][0] * val[pre[i][0]][0] % mod;
	}
	per(i, n, 1){
		if(pre[i][1] == -1) continue;
		val[i][1] = 1ll * val[i][1] * val[pre[i][1]][1] % mod;
	}
	rep(i, 1, n){
		if(pre[i][2] == -1) continue;
		val[i][2] = 1ll * val[i][2] * val[pre[i][2]][2] % mod;
	}
	per(i, n, 1){
		if(pre[i][3] == -1) continue;
		val[i][3] = 1ll * val[i][3] * val[pre[i][3]][3] % mod;
	}
	rep(i, 1, n){
		A[i] = 1ll * val[i][0] * val[i][1] % mod;
		B[i] = 1ll * val[i][2] * val[i][3] % mod;
		C_[i] = 1ll * val[i][0] * val[i][2] % mod;
		D[i] = 1ll * val[i][1] * val[i][3] % mod;
	}
	int ans = 0;
	per(i, n, 1) D[i] = (D[i] + D[i + 1]) % mod;
	rep(i, 1, n) ans = (ans + 1ll * C_[i] * D[i] % mod) % mod;
	sort(d + 1, d + n + 1, cmp);
	per(i, n, 1) E[i] = (E[i + 1] + B[d[i].y]) % mod;
	rep(i, 1, n) ans = (ans + 1ll * A[d[i].y] * E[i + 1] % mod) % mod;
	printf("%d", ans);
	return;
}
int main(){
    int qwq = 1; while(qwq--) mian();
    return 0;
}
```