526互联

[题解] CF1748E Yet Another Array Counting Problem

发布时间 2023-11-14 11:42:24作者: definieren

Yet Another Array Counting Problem

给你一个长度为 \(n\) 的序列和一个数 \(m\)，求有多少个长度为 \(n\) 的序列 \(b\) 满足：

  • \(\forall i \in [1, n], b_i \in [1, m]\)。
  • 对于每个区间 \([l, r]\)，\(b\) 中最大值最靠左的位置和 \(a\) 相同。

\(n, m \le 2 \times 10^5, n \times m \le 10^6\)。

看到数最大值的位置相同的数列个数，自然可以想到建笛卡尔树后树形 dp。

记 \(f_{u, i}\) 表示当前在节点 \(u\)，填的数是 \(i\) 的方案数，\(g_{u, i} = \sum_{j \le i} f_{u, j}\)。

此时的限制是左儿子中的数都小于当前节点的数，右儿子中的数都小于等于当前节点的数。所以转移是：

\[f_{u, i} \leftarrow g_{ls_u, i - 1} \times g_{rs_u, i} \]

然后直接转移就好了。

时间复杂度 \(O(nm)\)。

constexpr int MAXN = 2e5 + 9;
int n, m, a[MAXN], ls[MAXN], rs[MAXN];
vector<int> f[MAXN], stk;

void slv() {
	n = Read<int>(), m = Read<int>();
	for (int i = 1; i <= n; i ++) a[i] = Read<int>();
	for (int i = 1; i <= n; i ++) {
		while (stk.size() && a[stk.back()] < a[i])
			ls[i] = stk.back(), stk.pop_back();
		if (stk.size()) rs[stk.back()] = i;
		stk.emplace_back(i);
	}
	int rt = stk.front();
	function<void(int)> dp = [&](int u) {
		if (!u) return; f[u].resize(m + 1);
		dp(ls[u]), dp(rs[u]);
		for (int i = 1; i <= m; i ++) {
			f[u][i] = mul(f[ls[u]][i - 1], f[rs[u]][i]),
			cadd(f[u][i], f[u][i - 1]);
		}
		return;
	};
	f[0].resize(m + 1);
	for (int i = 0; i <= m; i ++) f[0][i] = 1;
	dp(rt);
	Write(f[rt][m], '\n');
	return;
}