「AtCoder Japan Alumni Group Summer Camp 2018 Day 2 K」Short LIS

题目链接:AtCoder Japan Alumni Group Summer Camp 2018 Day 2 K

给定 $n, a, b$,求满足如下条件的 $0 \sim n - 1$ 的排列 $P$ 的个数:

  • $P$ 的最长上升子序列的长度至多为 $2$。
  • $P_{a} = b$。

数据范围:$1 \le n \le 10 ^ {6}, 0 \le a, b < n$。


Solution

下文的 $b$ 均为 $n - b - 1$(最长下降子序列的长度至多为 $2$)。

最长下降子序列长度至多为 $2$ 有很多等价表述:

  • 可以划分成不超过 $2$ 个子序列,每个子序列单调上升。
  • 与前缀 $\max$ 序列一一对应
  • ……

对该排列建立递增单调栈,设栈内的序列为 $A$,其余数字组成的序列为 $B$,最长下降子序列长度至多为 $2$ 等价于 $A, B$ 序列均为递增序列(其中 $A$ 序列递增是必然的)。

  • 充分性:假如 $A, B$ 均为递增序列,显然最长下降子序列中不存在两个元素均在 $A$ 内或均在 $B$ 内,则其长度最多为 $2$。
  • 必要性:假如 $B$ 非递增,那么存在 $x < y, B_{x} > B_{y}$,一定可以找到 $A$ 中某个在 $x$ 之前的元素 $z$ 满足 $A_{z} > B_{x}$,此时最长下降子序列长度至少为 $3$。

于是,我们只需要构造出这个 $a_{1}, a_{2}, \ldots, a_{k}$ 满足 $a_{i}, P_{a_{i}}$ 数列均递增即可(其余数字递增填在空位)。放在坐标轴中就是一条折线

接下来考虑 $a, b$ 对这条折线有什么约束:

  • 当 $a \le b$ 时,这个数一定在单调栈中(体现在折线中即为拐点)。
  • 当 $a > b$ 时,这个数一定不在单调栈中(考虑反证),而我们将 $P$ 逆置换后可以得到一个对称性问题。

故这条折线满足:

  1. 从 $(0, 0)$ 出发到 $(n - 1, n - 1)$ 且每次只能向右、向上走。
  2. 不经过 $y = x$ 下方(不包括)。
  3. 必须经过点 $(a, b)$。

直接组合数容斥即可。

时间复杂度:$\mathcal O(n)$。


Code

#include <bits/stdc++.h>
typedef long long int64;

const int N = 2e6, MOD = 1e9 + 7;
int n, a, b, fac[N + 5], ifac[N + 5];

inline int power(int x, int k) {
    int ans = 1;
    for (; k > 0; k >>= 1, x = (int64)x * x % MOD) {
        if (k & 1) {
            ans = (int64)ans * x % MOD;
        }
    }
    return ans;
}
inline int inver(int x) {
    return power(x, MOD - 2);
}
void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = (int64)fac[i - 1] * i % MOD;
    }
    ifac[n] = inver(fac[n]);
    for (int i = n; i >= 1; i--) {
        ifac[i - 1] = (int64)ifac[i] * i % MOD;
    }
}
inline int binom(int n, int m) {
    return n < 0 || m < 0 || n < m ? 0 : (int64)fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}
inline int calc(int x1, int y1, int x2, int y2) {
    return binom(x2 - x1 + y2 - y1, x2 - x1);
}
int main() {
    scanf("%d%d%d", &n, &a, &b);
    init(n * 2);
    b = n - b - 1;
    if (a > b) {
        std::swap(a, b);
    }
    printf("%lld\n", ((int64)(calc(0, 0, a, b) - calc(1, -1, a, b)) * (calc(a, b, n - 1, n - 1) - calc(a, b, n, n - 2)) % MOD + MOD) % MOD);
    return 0;
}

2 条评论

  1. happydef

    是 可以划分成不超过 2 个子序列,每个子序列单调不升吧 /yiw

    1. Siyuan
      @happydef

      我改了个表述「最长下降子序列长度不超过 $2$」(因为不习惯最长上升 qaq),当然此处的「单调上升」也是针对排列而言的。

发表评论