自动搬运

查看原文

来自洛谷，原作者为

	ningago 恋爱脑

搬运于2025-08-24 22:53:51，当前版本为作者最后更新于2024-01-28 20:08:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

为方便表述，记 $R(f)$ 为 $f$ 的值域。

建立 $a$ 与 $b$ 的双射关系。题目中自然地有 $f:\{a\}\to\{ b\}$ 的映射，如果能为 $b$ 构造一个反映射 $g:R(f)\to\{a\}$（类似反三角），那么就可以从『计数本质不同的 $b$』转化为『求 $|R(g)|$』（由于 $g$ 是 $f$ 的反映射，故 $g$ 显然是单射）。

不妨使用贪心构造 $g$。对于某一个确定的 $b$，执行下列操作即可得到 $g(b)$：

• 初始时将 $a$ 中元素全部设置为 $+\infty$。
• 按权值从大到小遍历 $b$。
• 遍历到 $b_{[l,r]}=x$ 时，将对应的 $a$ 区间内的所有 $+\infty$ 设置为 $x$。
  • 若 $a$ 的对应区间内并不存在 $+\infty$（或已经设置过的 $x$），则代表这个 $b$ 并不存在于 $R(f)$ 中。
• 最后设置剩余的 $+\infty$ 为 $1$。

根据这个过程，可以尝试去判断某一个确定的 $a$ 是否存在于 $R(g)$ 中：

• 考虑 $a_x=1$ 的最小的 $x$。
  • 若不存在这样的 $x$，则说明所有的 $b$ 都有 $b_i>1$，且没有上述过程中『剩余的 $+\infty$』，也就是说条件为：所有 $b_i$ 的并集为 $[1,n]$。递归到『找最小 $a_x=2$ 』的子问题。
  • 否则，对于完全被 $[1,i-1]$ 包含的区间都有 $b_i>1$，而包含了 $i$ 的区间都有 $b_i\leq 1$。并且有条件：完全被 $[1,i-1]$ 包含的区间的并集恰好为 $[1,i-1]$（否则 $i$ 就不是最小的了）。递归到『找 $[1,i-1]$ 中最小 $a_x=2$』和 『找 $[1,n]$ 中次小 $a_x=1$（找 $[i+1,n]$ 中最小 $a_x=1$）』两个子问题。

普遍地，令 $dp_{l,r,p}$ 表示考虑区间 $[l,r]$，完全被 $[l,r]$ 包含的区间都有 $b_i\geq p$。令 $I_{l,r}$ 表示是否完全被 $[l,r]$ 包含的区间的并集恰好为 $[l,r]$。

则转移为：

• $dp_{l,r,p}\leftarrow I_{l,r}\times dp_{l,r,p+1}$
• $dp_{l,r,p}\leftarrow I_{l,i-1}\times dp_{l,i-1,p+1}\times dp_{i+1,r,p}$

此时复杂度为 $O(n^3c)$。

由于 DP 的转移过程是简单加乘，故不难发现，$dp_{l,r}$ 是一个次数为 $O(r-l)$ 的多项式 $F_{l,r}$，$dp_{l,r,p}$ 的取值为 $F_{l,r}(c-p+1)$（其中 $c-p+1$ 为 $dp_{l,r,p}$ 的迭代层数）。

在对 $c-p+1\geq O(n)$ 做区间 DP 后，用拉格朗日插值即可求出最终答案。

复杂度 $O(n^4)$。

#define N 110
int n, m, K;
int l_[N * N], r_[N * N];
bool ok[N][N]; int d[N];
int dp[N][N][N << 1];
int val[N << 1];

void solve()
{
	n = read(), m = read(), K = read();
	for(int i = 1; i <= m; i++) l_[i] = read(), r_[i] = read();
	for(int l = 1; l <= n; l++)
	{
		for(int r = l; r <= n; r++)
		{
			ok[l][r] = 1;
			for(int i = l - 1; i <= r + 1; i++) d[i] = 0;
			for(int i = 1; i <= m; i++) if(l <= l_[i] && r_[i] <= r) d[l_[i]]++, d[r_[i] + 1]--;
			for(int i = l; i <= r; i++) d[i] += d[i - 1], !d[i] && (ok[l][r] = 0);
		}
	}
	int tp = n + 5;
	for(int x = 1; x <= tp; x++)
	{
		for(int len = 1; len <= n; len++)
		{
			for(int l = 1, r = len; r <= n; l++, r++)
			{
				if(ok[l][r]) dp[l][r][x] = dp[l][r][x - 1];
				if(l == r) plus_(dp[l][r][x], 1);
				else plus_(dp[l][r][x], dp[l + 1][r][x]);
				if(l != r && ok[l][r - 1]) plus_(dp[l][r][x], dp[l][r - 1][x - 1]);
				for(int i = l + 1; i < r; i++)
					if(ok[l][i - 1])
						plus_(dp[l][r][x], 1ll * dp[l][i - 1][x - 1] * dp[i + 1][r][x] % mod);
			}
		}
		val[x] = dp[1][n][x];
	}
	if(K <= tp) { printf("%d\n", val[K]); return; }
	int ans = 0;
	for(int i = 1; i <= tp; i++)
	{
		int now = val[i];
		for(int j = 1; j <= tp; j++)
			if(i != j)
				mul_(now, sm(K + mod - j)), mul_(now, ksm(sm(i + mod - j), mod - 2));
		plus_(ans, now);
	}
	print(ans, '\n');
}