526互联

AtCoder Grand Contest 041 F Histogram Rooks

发布时间 2023-09-07 21:51:40作者: zltzlt

洛谷传送门

AtCoder 传送门

神题！！！！！！！！！/bx

全部格子都被覆盖不好处理，考虑钦定 \(k\) 个格子不被覆盖，容斥系数就是 \((-1)^k\)。

发现网格的行不一定连续，但是列是连续的。如果一列有格子被钦定，那么这一列就不能放棋子。

由此想到枚举不能放棋子的列（至少有一个棋子被钦定的列）集合 \(S\)，把每个行连续段的贡献相乘。

设行连续段有 \(len\) 个格子，其中 \(p\) 个格子所在列属于 \(S\)，那么如果这个行连续段没有格子被钦定，每个所在列不属于 \(S\) 的格子都能放棋子，贡献是 \(2^{len - p}\)；如果至少一个格子被钦定，枚举钦定了几个格子，得贡献为 \(\sum\limits_{i = 1}^p \binom{p}{i} (-1)^i = -[p > 0]\)。

但是很容易看出来一个问题，就是 \(S\) 中的列不一定至少有一个棋子被钦定。

仍然考虑容斥，钦定 \(T \subseteq S\) 为没有格子被钦定的列集合，容斥系数为 \((-1)^{|T|}\)；设行连续段中有 \(q\) 个格子所在列属于 \(T\)，那么如果这个行连续段没有格子被钦定，贡献仍然是 \(2^{len - p}\)；如果至少一个格子被钦定，贡献为 \(\sum\limits_{i = 1}^{p - q} \binom{p - q}{i} (-1)^i = -[p - q > 0] = -[p > q]\)。计算答案就把每个行连续段这样的贡献相乘即可。

枚举 \(S, T\) 复杂度显然过高，考虑简化。

首先我们发现只有连续段中 \(|S| = p, [|S| > |T|] = [p > q]\) 在计算贡献时有用。

然后考虑把网格按 \(h_i\) 的笛卡尔树剖分成若干个行连续段的贡献相同的形式，像这样（图来自 Verdandi）：

建出笛卡尔树，发现相邻的色块（父亲与儿子）相互依赖。比如上图，绿色块的 \(p\) 等于第 \(1, 3, 5\) 列是否被 \(S\) 包含加上橙色块的 \(p\) 加上黄色块的 \(p\) 加上粉色块的 \(p\)，同理，\([p > q]\) 是所有子结点的 \([p > q]\) 的或（或者可以维护 \([p = q]\)，就是所有子结点的 \([p = q]\) 的与）。

考虑一个树形 dp，\(f_{u, i, 0/1}\) 表示 \(u\) 结点目前 \(p = i\)，\([p = q] = 0/1\) 的容斥系数 \((-1)^{|T|}\) 乘贡献之和。我们首先考虑空行，也就是 \(f_{u, 0, 0} = f_{u, 1, 0} = 1, f_{u, 1, 1} = -1\)（对于 \(h_i\) 相同的子结点强制钦定一个父子顺序）。然后树形背包合并上来子结点。最后乘上若干行（设为 \(b_u\)）连续段的贡献，也就是 \((2^{sz_u - p} - [p > q])^{b_u}\)。

快速幂计算贡献是 \(O(n^2 \log n)\)，容易通过预处理这个贡献做到 \(O(n^2)\)。

code 
// Problem: F - Histogram Rooks
// Contest: AtCoder - AtCoder Grand Contest 041
// URL: https://atcoder.jp/contests/agc041/tasks/agc041_f
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 410;
const int logn = 10;
const ll mod = 998244353;

ll n, a[maxn], stk[maxn], top, L[maxn], R[maxn], pw[maxn][maxn][2];
pii h[maxn][logn];
bool vis[maxn];
vector<int> G[maxn];

inline pii qmin(int l, int r) {
	int k = __lg(r - l + 1);
	return min(h[l][k], h[r - (1 << k) + 1][k]);
}

int build(int l, int r) {
	if (l > r) {
		return 0;
	}
	int mid = qmin(l, r).scd;
	int p = build(l, mid - 1), q = build(mid + 1, r);
	if (p) {
		G[mid].pb(p);
	}
	if (q) {
		G[mid].pb(q);
	}
	return mid;
}

ll f[maxn][maxn][2], sz[maxn], g[maxn][2], b[maxn];

inline void upd(ll &x, ll y) {
	((x += y) >= mod) && (x -= mod);
}

void dfs(int u) {
	sz[u] = 1;
	f[u][0][1] = f[u][1][0] = 1;
	f[u][1][1] = mod - 1;
	for (int v : G[u]) {
		b[v] = a[v] - a[u];
		dfs(v);
		for (int i = 0; i <= sz[u]; ++i) {
			g[i][0] = f[u][i][0];
			g[i][1] = f[u][i][1];
			f[u][i][0] = f[u][i][1] = 0;
		}
		for (int i = 0; i <= sz[u]; ++i) {
			for (int j = 0; j <= sz[v]; ++j) {
				upd(f[u][i + j][1], g[i][1] * f[v][j][1] % mod);
				upd(f[u][i + j][0], (g[i][1] * f[v][j][0] % mod + g[i][0] * (f[v][j][0] + f[v][j][1]) % mod) % mod);
			}
		}
		sz[u] += sz[v];
	}
	for (int i = 0; i <= sz[u]; ++i) {
		f[u][i][0] = f[u][i][0] * pw[sz[u] - i][b[u]][0] % mod;
		f[u][i][1] = f[u][i][1] * pw[sz[u] - i][b[u]][1] % mod;
	}
}

void solve() {
	scanf("%lld", &n);
	ll k = 1;
	for (int i = 0; i <= n; ++i) {
		pw[i][0][0] = pw[i][0][1] = 1;
		for (int j = 1; j <= n; ++j) {
			pw[i][j][0] = pw[i][j - 1][0] * (k + mod - 1) % mod;
			pw[i][j][1] = pw[i][j - 1][1] * k % mod;
		}
		k = k * 2 % mod;
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
		h[i][0] = mkp(a[i], i);
	}
	for (int j = 1; (1 << j) <= n; ++j) {
		for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
			h[i][j] = min(h[i][j - 1], h[i + (1 << (j - 1))][j - 1]);
		}
	}
	int rt = build(1, n);
	b[rt] = a[rt];
	dfs(rt);
	ll ans = 0;
	for (int i = 0; i <= n; ++i) {
		upd(ans, f[rt][i][0]);
		upd(ans, f[rt][i][1]);
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}