题意理解 我们有：

N N 头奶牛，大小分别为 s 1 , s 2 , … , s N s 1 ​ ,s 2 ​ ,…,s N ​

N N 个牛棚，大小分别为 t 1 , t 2 , … , t N t 1 ​ ,t 2 ​ ,…,t N ​

奶牛 i i 能进入牛棚 j j 当且仅当 s i ≤ t j s i ​ ≤t j ​ 。

一个 匹配 是一些奶牛与牛棚的配对，每头奶牛最多匹配一个牛棚，每个牛棚最多匹配一头奶牛。

一个匹配是 极大的，如果：

所有被匹配的奶牛都能进入分配给它的牛棚；

对于任意未被匹配的奶牛，它不能进入任意未被匹配的牛棚（即剩下的牛棚它都进不去）。

我们要数 极大匹配的数量（模 10 9 + 7 10 9 +7）。

样例分析 样例：

text N = 4 s = 1 2 3 4 t = 1 2 2 3 输出 9，并给出了 9 种极大匹配。

思路推导

1. 排序与匹配可行性 首先，我们可以把 s s 和 t t 分别排序，因为匹配只与大小关系有关。

排序后，奶牛 i i 能匹配的牛棚是一个后缀（因为如果 s i ≤ t j s i ​ ≤t j ​ ，则对 t j + 1 t j+1 ​ 也成立，如果 t t 升序排列）。

2. 极大匹配的条件 极大匹配意味着：

没有被匹配的奶牛，必须比所有未被匹配的牛棚大（即无法进入任何一个剩下的牛棚）。

等价地，如果我们将奶牛按大小升序排列，牛棚也升序排列，那么未被匹配的奶牛一定是最大的若干头，未被匹配的牛棚一定是最小的若干头，并且未被匹配的奶牛全都大于未被匹配的牛棚。

3. 动态规划状态设计 我们考虑将 奶牛和牛棚放在一起排序，但标记它是奶牛还是牛棚。

设 a a 是一个长度为 2 N 2N 的数组，每个元素是 ( v a l u e , t y p e ) (value,type)，type=0 表示奶牛，type=1 表示牛棚。按 value 升序排序，value 相同时牛棚排在前面（这样保证 value 相等时奶牛可以匹配这个牛棚）。

我们定义 DP 状态：

d p [ i ] [ j ] [ 0 / 1 ] dp[i][j][0/1] 表示：

处理完前 i i 个元素（奶牛或牛棚）

当前有 j j 头奶牛还未被匹配（等待匹配后面的牛棚）

第三维 0/1 表示是否已经有“未被匹配的奶牛”（即是否已经开始了“极大匹配”的未匹配部分）

状态转移：

遇到奶牛（type=0）：

可以匹配后面的牛棚： d p [ i ] [ j + 1 ] [ 0 ]

= d p [ i − 1 ] [ j ] [ 0 ] dp[i][j+1][0] +=dp[i−1][j][0]

也可以选择不匹配它（作为未匹配的奶牛），但一旦不匹配，后面所有牛棚它都不能匹配（因为排序后牛棚 value 更大或相等，但排序规则保证牛棚在前，所以这里不匹配意味着它大于所有后面未匹配牛棚？这里要小心）—— 实际上，不匹配这头奶牛时，必须保证它不能进入任何未匹配的牛棚，所以只有当我们已经决定不匹配它时，后面不能有未匹配的牛棚 value ≥ 它。但我们的 DP 设计是通过“未匹配奶牛数 j” 和 “是否已经开始未匹配” 来控制的。

更常见的做法（参考官方题解）： 我们定义 d p [ i ] [ j ] [ k ] dp[i][j][k]：

i: 考虑前 i 个元素（奶牛和牛棚混排）

j: 当前还有 j 个牛棚未被匹配（等待奶牛）

k=0: 还未开始“未匹配奶牛”阶段

k=1: 已经开始了“未匹配奶牛”阶段（即已经有不匹配的奶牛）

转移：

遇到奶牛：

匹配一个未来的牛棚： d p [ i ] [ j + 1 ] [ k ]

= d p [ i − 1 ] [ j ] [ k ] dp[i][j+1][k] +=dp[i−1][j][k]（增加一个等待匹配的牛棚数？不对，这里要仔细）

实际上更清晰的做法是： 把奶牛和牛棚分开排序，然后用双序列 DP。

常见 AC 做法 设 d p [ i ] [ j ] dp[i][j] 表示：

考虑了前 i 头奶牛（按 s 升序）

匹配了前 j 个牛棚（按 t 升序）

并且保证是极大匹配的方案数

但这样还不够，因为极大匹配要求未被匹配的奶牛不能进入未被匹配的牛棚。

更简洁的做法（参考已知题解）： 将 s 和 t 排序，然后使用 DP： 定义 f ( i , j ) f(i,j) 表示：

已经考虑了前 i 头奶牛和前 j 个牛棚

并且满足极大匹配条件的方案数

转移时考虑第 i 头奶牛是否匹配：

如果匹配，则匹配一个牛棚 k（k>j 且 t_k ≥ s_i）

如果不匹配，则必须保证 s_i > 所有未匹配的牛棚（即 t_{j+1} 到 t_N 都 < s_i）

这样复杂度 O(N^3) 需要优化。

O(N^2) 解法 将奶牛和牛棚放在一起按值升序排序，值相同时牛棚在前。

定义 d p [ i ] [ j ] [ 0 / 1 ] dp[i][j][0/1]：

i: 考虑前 i 个元素

j: 当前未匹配的奶牛数

flag=0: 还没有未匹配的奶牛（即所有奶牛都匹配或暂未决定）

flag=1: 已经有未匹配的奶牛（即后面的牛棚不能再匹配任何奶牛）

转移：

当前是牛棚：

可以匹配一个未匹配奶牛（j>0）：dp[i][j-1][flag] += dp[i-1][j][flag] * j

也可以不匹配（留给后面）：dp[i][j][flag] += dp[i-1][j][flag]（但若 flag=1 则不能匹配后面奶牛，所以牛棚必须空？这里要再细想）

实际上，更清晰的： 设 d p [ i ] [ j ] dp[i][j] = 考虑前 i 个元素，有 j 个奶牛还未匹配，且满足极大匹配条件的方案数。

初始化 dp[0][0] = 1。

遍历 i = 1..2N：

若 a[i] 是牛棚：

匹配一个等待的奶牛：dp[i][j-1] += dp[i-1][j] * j（j>0）

不匹配（留给后面）：dp[i][j] += dp[i-1][j]

若 a[i] 是奶牛：

匹配后面的牛棚：dp[i][j+1] += dp[i-1][j]

不匹配（作为极大匹配中的未匹配者）：只有当后面所有牛棚都 < 该奶牛时才合法，但这里我们可以在排序后通过“牛棚在前”保证，所以不匹配时，必须保证该奶牛 > 所有未匹配牛棚，即后面没有牛棚 value ≥ 它。由于排序规则，value 相等时牛棚在前，所以如果当前是奶牛且前面有未匹配牛棚 value ≥ 它，则不能不匹配。因此，不匹配操作只能在“没有未匹配牛棚”时进行，即 j=0 时：dp[i][j] += dp[i-1][j]（这里 j=0）

最终答案 = dp[2N][0]。

最终 AC 代码框架 cpp #include <bits/stdc++.h> using namespace std; const int MOD = 1e9+7; const int N = 3005;

int n; int s[N], t[N]; pair<int,int> a[2N]; // value, type: 0=cow, 1=shed int dp[2N][N];

int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> s[i]; a[i] = {s[i], 0}; } for (int i = 0; i < n; i++) { cin >> t[i]; a[n+i] = {t[i], 1}; } sort(a, a + 2*n, [](const pair<int,int>& x, const pair<int,int>& y) { if (x.first != y.first) return x.first < y.first; return x.second > y.second; // 牛棚在前 (1 > 0) });

dp[0][0] = 1;
for (int i = 0; i < 2*n; i++) {
    for (int j = 0; j <= n; j++) {
        if (!dp[i][j]) continue;
        if (a[i].second == 1) { // 牛棚
            // 匹配一个等待的奶牛
            if (j > 0) dp[i+1][j-1] = (dp[i+1][j-1] + 1LL * dp[i][j] * j) % MOD;
            // 不匹配，留给后面
            dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD;
        } else { // 奶牛
            // 匹配后面的牛棚
            dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % MOD;
            // 不匹配（作为未匹配奶牛），只有当 j=0 时才可以
            if (j == 0) dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD;
        }
    }
}
cout << dp[2*n][0] << endl;
return 0;

} 总结 核心：将奶牛和牛棚混合排序，牛棚在前。

DP 状态：处理到第 i 个元素，有 j 个奶牛等待匹配。

转移时注意极大匹配的条件：只有没有等待匹配的牛棚时，奶牛才能选择不匹配。

时间复杂度 O(N²)，空间可滚动数组优化。