P5469 [NOI2019] 机器人 题解

Description

小 R 喜欢研究机器人。

最近，小 R 新研制出了两种机器人，分别是 P 型机器人和 Q 型机器人。现在他要测试这两种机器人的移动能力，测试在从左到右排成一排的 $n$ 个柱子上进行，柱子用 $1 - n$ 依次编号，$i$ 号柱子的高度为一个正整数 $h_i$。机器人只能在相邻柱子间移动，即：若机器人当前在 $i$ 号柱子上，它只能尝试移动到 $i - 1$ 号和 $i + 1$ 号柱子上。

每次测试，小 R 会选取一个起点 $s$，并将两种机器人均放置在 $s$ 号柱子上。随后它们会按自己的规则移动。

P 型机器人会一直向左移动，但它无法移动到比起点 $s$ 更高的柱子上。更具体地，P 型机器人在 $l (l \leq s)$ 号柱子停止移动，当且仅当下列两个条件均成立：

• $l = 1$ 或 $h_{l-1} > hs$。

• 对于满足 $l \leq j \leq s$ 的 $j$，有 $h_j \leq h_s$。

Q 型机器人会一直向右移动，但它只能移动到比起点 $s$ 更低的柱子上。更具体地，Q 型机器人在 $r (r \geq s)$ 号柱子停止移动，当且仅当下列两个条件均成立：

• $r = n$ 或 $h_{r+1} \geq h_s$。

• 对于满足 $s < j \leq r$ 的 $j$，有 $h_j < h_s$。

现在，小 R 可以设置每根柱子的高度，$i$ 号柱子可选择的高度范围为 $[A_i, B_i]$，即 $A_i \leq h_i \leq B_i$。小 R 希望无论测试的起点 $s$ 选在哪里，两种机器人移动过的柱子数量的差的绝对值都小于等于 $2$。他想知道有多少种柱子高度的设置方案满足要求，小 R 认为两种方案不同当且仅当存在一个 $k$，使得两种方案中 $k$ 号柱子的高度不同。请你告诉他满足要求的方案数模 $10^9 + 7$ 后的结果。

$1 \leq n \leq 300$ , $1 \leq A_i \leq B_i \leq 10^9$。

Solution

不妨设当前要求区间 $[l,r]$ 的方案，最高的柱子的位置为 $p$（如果有相同的取最右边的那个），那么这个柱子一定满足 $|(p-l)-(r-p)|\leq 2$，并且这个柱子将整个序列划分成了两个互相没有关系的连续子序列，这样就可以 dp 了。

设 $f_{l,r,k}$ 表示区间 $[l,r]$ 的最大值不超过 $k$ 的方案数，可以得到转移：

$$f_{l,r,k}=f_{l,r,k-1}+\sum_{\left [\left|(i-l)-(r-i)\right|\leq 2\right]}{f_{l,i-1,k}f_{i+1,r,k-1}}$$

容易发现转移点是 $O(1)$ 级别的，所以时间复杂度为：$O(n^2V)$。

---

考虑优化。

注意到我们只需要求 $[1,n]$ 的答案，所以在求解 dp 的过程中很多状态都是无意义的，暴搜发现用到的区间最多 $2047$ 个，只需要对这些区间 dp 即可。

设有 $m$ 个用到的区间，时间复杂度就优化为了 $O(mV)$。

---

但这样还不够，现在需要把时间复杂度中的值域去掉。

考虑之前为什么需要枚举值域，这是因为对于不同的最大值，包含它的柱子是不一样的，就会导致转移方程不一样。

注意到不同的转移只有 $O(n)$ 种，所以可以离散化然后对于每个转移一样的连续段 $[L,R]$ 进行转移。

修改状态为 $f_{i,j}$ 表示第 $i$ 个区间，最大值不超过 $L+j-1$ 的方案数。可以得到转移：

$$f_{i,j}=f_{i,j-1}+\sum_{k\in \text{next}_i}{f_{x_k,j}f_{y_k,j-1}}$$

由于每个 $f_{i,j}$ 的转移式和 $f_{i,j-1}$ 的转移式除了第一维是一样的，所以 $f_{i,j}$ 可以表示为有关 $j$ 的 $R_i-L_i+1$ 次多项式。证明就考虑归纳法，如果 $f_{i,0},f_{i,1}\ldots f_{i,j-1}$ 的多项式系数一样，那么 $f_{i,j}$ 由于与之前这 $j$ 个 dp 的转移是一模一样的，所以其系数也和这些一样。

所以对于每个 $f_{i}$ 只需要维护 $f_{i,0},f_{i,1},\ldots f_{i,R_i-L_i+1}$ 的值，就可以插值求出 $f_{i,R-L+1}$。

时间复杂度：$O(n^2m)$。

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 305, kMaxM = 3e3 + 5, kMod = 1e9 + 7;

int n, m, cnt;
int l[kMaxN], r[kMaxN], unq[kMaxN * 2], id[kMaxN][kMaxN];
int f[kMaxM][kMaxN], g[kMaxM], fac[kMaxN], ifac[kMaxN], inv[kMaxN];
std::pair<int, int> seg[kMaxM];
std::vector<std::tuple<int, int, int>> nxt[kMaxM];

constexpr int qpow(int bs, int64_t idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
    if (idx & 1)
      ret = (int64_t)ret * bs % kMod;
  return ret;
}

inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

void dfs(int l, int r) {
  static bool vis[kMaxN][kMaxN];
  if (l > r || vis[l][r]) return;
  seg[++cnt] = {l, r}, vis[l][r] = 1;
  for (int i = l; i <= r; ++i) {
    if (abs(i - l - (r - i)) <= 2) {
      dfs(l, i - 1), dfs(i + 1, r);
    }
  }
}

void gettrans() {
  dfs(1, n);
  std::sort(seg + 1, seg + 1 + cnt, [&] (std::pair<int, int> &p1, std::pair<int, int> &p2) { return p1.second - p1.first > p2.second - p2.first; });
  for (int i = 1; i <= cnt; ++i) id[seg[i].first][seg[i].second] = i;
  for (int i = 1; i <= cnt; ++i) {
    auto [l, r] = seg[i];
    for (int j = l; j <= r; ++j)
      if (abs(j - l - (r - j)) <= 2)
        nxt[i].emplace_back(j, id[l][j - 1], id[j + 1][r]);
  }
}

int getinv(int x) { return x > 0 ? inv[x] : sub(0, inv[-x]); }

void discrete() {
  std::sort(unq + 1, unq + 1 + m);
  m = std::unique(unq + 1, unq + 1 + m) - (unq + 1);
  fac[0] = ifac[0] = 1;
  for (int i = 1; i <= n + 3; ++i) {
    inv[i] = qpow(i);
    fac[i] = 1ll * i * fac[i - 1] % kMod;
    ifac[i] = 1ll * inv[i] * ifac[i - 1] % kMod;
  }
}

void prework() {
  for (int i = 1; i <= n; ++i) unq[++m] = l[i], unq[++m] = r[i] + 1;
  discrete(), gettrans();
}

int getval(int *x, int n, int k) {
  static int pre[kMaxN], suf[kMaxN];
  int ans = 0;
  pre[0] = suf[n + 1] = 1;
  for (int i = 1; i <= n; ++i) pre[i] = 1ll * pre[i - 1] * sub(k, i) % kMod;
  for (int i = n; i; --i) suf[i] = 1ll * suf[i + 1] * sub(k, i) % kMod;
  for (int i = 1; i <= n; ++i) {
    int coef = 1ll * pre[i - 1] * suf[i + 1] % kMod * ifac[i - 1] % kMod * ifac[n - i] % kMod;
    if ((n - i) & 1) coef = sub(0, coef);
    inc(ans, 1ll * coef * x[i] % kMod);
  }
  return ans;
}

void solve(int L, int R) {
  for (int i = cnt; i; --i) {
    for (int j = 1; j <= n + 3; ++j) {
      f[i][j] = f[i][j - 1];
      for (auto [p, x, y] : nxt[i]) {
        if (L >= l[p] && R <= r[p]) {
          inc(f[i][j], 1ll * f[x][j] * f[y][j - 1] % kMod);
        }
      }
    }
  }
  for (int i = 1; i <= cnt; ++i) f[i][0] = getval(f[i], seg[i].second - seg[i].first + 2, R - L + 1);
}

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i <= n; ++i) std::cin >> l[i] >> r[i];
  prework();
  std::fill_n(f[0], n + 4, 1);
  for (int i = 1; i < m; ++i) solve(unq[i], unq[i + 1] - 1);
  std::cout << f[1][0] << '\n';
}

int32_t main() {
  freopen("robot.in", "r", stdin);
  freopen("robot.out", "w", stdout);
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}