题目链接：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;
}