题解：AT_jag2018summer_day2_k Short LIS

Phartial · 2025-04-20 15:08:10 · 题解

先翻转整个排列，根据 Dilworth 定理，最长下降子序列长度不超过 2 等价于可以用两条上升子序列覆盖 p。

注意到，如果可以用两条上升子序列覆盖 p，那么一定有一种覆盖方案，使得其中一条子序列恰好覆盖了 p 的所有前缀最大值。

证明：前缀最大值肯定能构成一个上升子序列，如果剩下的数不是单调递增的，就必然有一对非前缀最大值 p_i,p_j 满足 p_i>p_j，找到 p_i 之前的第一个前缀最大值 p_k，就有 p_k>p_i>p_j，最长下降子序列长度超过 2，不满足性质。因此如果不能用一条上升子序列覆盖所有非前缀最大值，就不可能存在用两条上升子序列覆盖 p 的方案。

如果确定了 p 中的前缀最大值，那么为了让剩下的数单调递增，我们至多只有一种填数的方法，故我们只需要关心 p 的前缀最大值。

显然有 \displaystyle\max_{i=1}^k p_i\ge k，这启示我们用折线的方式刻画 p。连接 \displaystyle(k-1,\max_{i=1}^k p_i) 和 \displaystyle(k,\max_{i=1}^k p_i)，并用竖线连接每个段得到一条 (0,0) 到 (n,n) 的折线。则易证所有不穿过 y=x 的折线和所有合法的排列构成双射。

现在只需要处理 p_A=B 的限制了，不难发现在所有合法的方案里 p_k 为前缀最大值的充要条件是 p_k\ge k，证明：

• 若前缀最大值 p_k<k，则 p_{1\dots k-1} 中必有一个数大于 p_k，p_k 不是前缀最大值，矛盾；
• 反之，若某个非前缀最大值 p_k\ge k，则 p_{k+1\dots n} 中必有一个数小于 p_k，方案不合法，矛盾。

因此若 B\ge A，p_A 就必然是 p 的前缀最大值，所以折线中需要出现 (A-1,B-1)-(A-1,B)-(A,B) 这一子段。拆成 (0,0)-(A-1,B-1) 的折线与 (A,B)-(n,n) 的折线分开统计方案数即可。

若 B<A，考虑计数 p 的逆排列 q，对 q 的限制仍然是需要用两条上升子序列覆盖，所以处理方法是一样的。但此时就有 A\ge B，所以可以套用上面的处理方法。

#include <iostream>
#include <atcoder/modint>

using namespace std;
using ll = atcoder::modint1000000007;

const int kN = 2e6 + 1;

int n, a, b;
ll ans, f[kN];

ll C(int n, int m) { return m < 0 ? 0 : f[n] / f[m] / f[n - m]; }
ll F(int p, int q) { return C(p + q, p) - C(p + q, p - 1); }

int main() {
  cin.tie(0)->sync_with_stdio(0);
  f[0] = 1;
  for (int i = 1; i < kN; ++i) {
    f[i] = f[i - 1] * i;
  }
  cin >> n >> a >> b, a = n - a, ++b;
  if (b < a) {
    swap(a, b);
  }
  cout << (F(a - 1, b - 1) * F(n - b, n - a)).val();
  return 0;
}