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;
}
- 题解 Counting Another Problem 1748E题解counting another problem 数论counting another problem 题解permutation another problem 题解another problem 1870e 题解another maxflow problem 题解another algebra problem 题解minimization another problem 题解inversions another problem 题解counting t399753 problem 题解counting problem simple