这里我用 $C_{n}^{m}$ 表示”从 $n$ 个不同的数里选出 $m$ 个数的组合方案数”。

首先考虑 $x \gt y$ 的情况，此时我们只需要执行：

• $i \leftarrow n+1-i$
• $j \leftarrow n+1-j$
• $x, y \leftarrow y,x$（即交换 $x$ 和 $y$ 的值）

就能将问题转成 $x \lt y$ 的情况了。

所以下面就只需要针对 $x \lt y$ 的情况做展开。

有两种情况需要分开来讨论：

• 情况1：$y = n$
• 情况2：$y \lt n$

情况1：$y = n$

此时情况如下：

首先可以确定的是 $a_i = x, a_j = y = n$，所以区间 $[1, j]$ 是递增的，区间 $[j,n]$ 是递减的。

可以把区间 $[1, n]$ 划分成三部分：

• 第 $1$ 部分：区间 $[1, i-1]$ （即 $a_i$ 左边那些数）一共有 $i-1$ 个位置
• 第 $2$ 部分：区间 $[i+1, j-1]$ （即 $a_i$ 和 $a_j$ 中间那些数）一共有 $j-i-1$ 个位置
• 第 $3$ 部分：区间 $[j+1, n]$（即 $a_j$ 右边那些数）一共有 $n-j$ 个位置

首先考虑第 $2$ 部分，因为从 $a_i$ 到 $a_j$ 是递增的，所以这一部分能够选的数的范围是 $[x+1, n-1]$，所以这一部分我们要从 $[x+1, n-1]$ 这 $n-x-1$ 个数里面选 $j-i-1$ 个数，对应的方案数为 $C_{n-x-1}^{j-i-1}$。

然后再考虑第 $1$ 部分，这一部分的数都应该 $\lt x$，可以选的数有 $x-1$ 个，需要选择 $i-1$ 个数，对应的方案数为 $C_{x-1}^{i-1}$。

第 $1$、$2$ 部分确定好之后，第 $3$ 部分自然就确定了。

所以，当 $y = n$ 时，总的方案数为：

$C_{n-x-1}^{j-i-1} \cdot C_{x-1}^{i-1}$

当然，若 $n-x-1 \lt j-i-1$ 或者 $x-1 \lt i-1$，则方案数为 $0$。

情况2：$y \lt n$

此时又要分两种情况讨论，设最大值为 $a_k$，则 $k$ 有两种情况：

• 情况(1)： $i \lt k \lt j$（可以从 $i+1$ 到 $j-1$ 枚举 $k$）
• 情况(2)： $j \lt k \lt n$（可以从 $j+1$ 到 $n-1$ 枚举 $k$）

情况(1) $i \lt k \lt j$

此时情况如下：

可以把区间 $[1, n]$ 划分成四部分：

• 第 $1$ 部分：区间 $[1,i-1]$（即 $a_i$ 左边那些数）一共有 $i-1$ 个位置
• 第 $2$ 部分：区间 $[i+1, k-1]$（即 $a_i$ 和 $a_k$ 中间那些数）一共有 $k-i-1$ 个位置
• 第 $3$ 部分：区间 $[k+1, j-1]$（即 $a_k$ 和 $a_j$ 中间那些数）一共有 $j-k-1$ 个位置
• 第 $4$ 部分：区间 $[j+1, n]$（即 $a_j$ 右边那些数）一共有 $n-j$ 个位置

先考虑第 $3$ 部分，这一部分需要从 $[y+1, n-1]$ 这 $n-y-1$ 个数中选出 $j-k-1$ 个数，对应的方案数为 $C_{n-y-1}^{j-k-1}$。

然后再考虑第 $2$ 部分，这一部分需要所有 $\gt x$ 的数，但是区间 $[k, j]$ 已经占去了 $j-k+1$ 个数字（其中区间 $[k+1,j-1]$ 占去了 $j-k-1$ 个，$a_i$ 和 $a_j$ 各占去了一个），剩下可选的 $\gt x$ 的数还有 $(n - x) - (j-k+1) = n-x-j+k-1$ 个数，需要从这些数里选出恰好 $k-i-1$ 个数放在区间 $[i+1, k-1]$ 中，对应的方案数为 $C_{n-x-j+k-1}^{k-i-1}$。

然后再考虑第 $1$ 部分，这一部分和第 $2$、$3$ 部分是没有冲突的，可以选的数有 $x-1$ 个，需要选择 $i-1$ 个数，对应的方案数为 $C_{x-1}^{i-1}$。

对于任意一个 $i \lt k \lt j$，对应的方案数是：

$C_{n-y-1}^{j-k-1} \cdot C_{n-x-j+k-1}^{k-i-1} \cdot C_{x-1}^{i-1}$

总方案数为：

$\sum\limits_{k=i+1}^{j-1} C_{n-y-1}^{j-k-1} \cdot C_{n-x-j+k-1}^{k-i-1} \cdot C_{x-1}^{i-1}$

情况(2)： $j \lt k \lt n$

此时情况如下：

可以把区间 $[1, n]$ 划分成四部分：

• 第 $1$ 部分：区间 $[1, i-1]$（即 $a_i$ 左边那些数） 一共有 $i-1$ 个位置
• 第 $2$ 部分：区间 $[i+1, j-1]$（即 $a_i$ 和 $a_j$ 中间那些数） 一共有 $j-i-1$ 个位置
• 第 $3$ 部分：区间 $[j+1, k-1]$（即 $a_j$ 和 $a_k$ 中间那些数） 一共有 $k-j-1$ 个位置
• 第 $4$ 部分：区间 $[k+1, n]$（即 $a_k$ 右边那些数） 一共有 $n-k$ 个位置

然后我们会发现，第 $1$、$2$、$3$ 部分所选择的数的范围是没有重叠的，所以：第一部分选数的方案数为 $C_{x-1}^{i-1}$；第二部分选数的方案数为 $C_{y-x-1}^{j-i-1}$；第三部分选数的方案数为 $C_{n-y-1}^{k-j-1}$，前 $3$ 部分确定下来了，第四部分也就确定了。

对于任意一个 $j \lt k \lt n$，对应的方案数是：

$C_{x-1}^{i-1} \cdot C_{y-x-1}^{j-i-1} \cdot C_{n-y-1}^{k-j-1}$

总方案数为：

$\sum\limits_{k=i+1}^{n-1} C_{x-1}^{i-1} \cdot C_{y-x-1}^{j-i-1} \cdot C_{n-y-1}^{k-j-1}$

结合两部分的情况，总的方案数是：

$\sum\limits_{k=i+1}^{j-1} C_{n-y-1}^{j-k-1} \cdot C_{n-x-j+k-1}^{k-i-1} \cdot C_{x-1}^{i-1} + \sum\limits_{k=i+1}^{n-1} C_{x-1}^{i-1} \cdot C_{y-x-1}^{j-i-1} \cdot C_{n-y-1}^{k-j-1}$

然后代码实现的时候会有些情况的组合数不合法，不合法的组合数均视为 $0$ 即可。

下面是我的代码：

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const int maxn = 110;
long long c[maxn][maxn];

void init() {
    c[0][0] = 1;
    for (int i = 1; i < maxn; i++) {
        for (int j = 0; j <= i; j++) {
            if (!j || j==i) c[i][j] = 1;
            else c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
        }
    }
}

long long cal(int n, int i, int j, int x, int y) {
    if (x > y) {    // 如果 x > y，调整一下 i 和 j 的位置，这样只用处理 x < y 的两种情况就可以了
        i = n + 1 - i;
        j = n + 1 - j;
        swap(x, y);
    }
    if (y == n) {   // y == n 的情况特判
        return c[n-x-1][j-i-1] * c[x-1][i-1] % MOD;
    }
    // 接下来分析 x < y < n 的情况
    long long sum = 0;
    for (int k = i+1; k < j; k++)
        sum = (sum + c[n-y-1][j-k-1] * c[n-x-j+k-1][k-i-1] % MOD * c[x-1][i-1] % MOD) % MOD;
    for (int k = j+1; k < n; k++)
        sum = (sum + c[x-1][i-1] * c[y-x-1][j-i-1] % MOD * c[n-y-1][k-j-1] % MOD) % MOD;
    return sum;
}

int T, n, i, j, x, y;

int main() {
    init();
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d%d%d", &n, &i, &j, &x, &y);
        printf("%lld\n", cal(n, i, j, x, y));
    }
    return 0;
}

但是样例的最后一组就出错了，样例输出是 4788，我的输出是 7308。

请问我是哪里考虑错了吗？