P10008 [集训队互测 2022] Range Minimum Element

ningago · 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');
}