Counting Orders
题面翻译
求有多少种重新排列 \(a\) 的方式，使得对于任意 \(1\le i\le n\)，都满足 \(a_i>b_i\)，结果对 \(10^9+7\) 取模。
\(1\le n\le 2\times 10^5,1\le a_i,b_i\le 10^9\)，保证 \(a_i\) 互不相同。
题目描述
You are given two arrays $ a $ and $ b $ each consisting of $ n $ integers. All elements of $ a $ are pairwise distinct.
Find the number of ways to reorder $ a $ such that $ a_i > b_i $ for all $ 1 \le i \le n $ , modulo $ 10^9 + 7 $ .
Two ways of reordering are considered different if the resulting arrays are different.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.
The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^{5} $ ) — the length of the array $ a $ and $ b $ .
The second line of each test case contains $ n $ distinct integers $ a_1 $ , $ a_2 $ , $ \ldots $ , $ a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the array $ a $ . It is guaranteed that all elements of $ a $ are pairwise distinct.
The second line of each test case contains $ n $ integers $ b_1 $ , $ b_2 $ , $ \ldots $ , $ b_n $ ( $ 1 \le b_i \le 10^9 $ ) — the array $ b $ .
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^{5} $ .
输出格式
For each test case, output the number of ways to reorder array $ a $ such that $ a_i > b_i $ for all $ 1 \le i \le n $ , modulo $ 10^9 + 7 $ .
样例 #1
样例输入 #1
5
6
9 6 8 4 5 2
4 1 5 6 3 1
3
4 3 2
3 4 9
1
2
1
3
2 3 4
1 3 3
12
2 3 7 10 23 28 29 50 69 135 420 1000
1 1 2 3 5 8 13 21 34 55 89 144
样例输出 #1
32
0
1
0
13824
分析
常理来说，我们肯定要先解决 \(b\) 里边大的数，所以我们把 \(b\) 降序排列，保证大的数先被遍历到，同时我们肯定希望在合法的前提下，能先尽可能考虑 \(a\) 里边小的数，所以我们把 \(a\) 升序排列
然后遍历 \(b\) ，对于 \(b[i]\)，我们找到 \(a\) 中第一个大于 \(b[i]\) 的数记 \(a[k]\) ，\(a\) 中有 \((n - k)\) 个数大于 \(b[i]\) ，因为 \(b\) 降序，所以 \(n-k\) 个数中有一些已经被分配去对抗大于 \(b[i]\) 的 数，遍历到 \(b[i]\) 时 \(a\) 中就有 \(i\) 个数被分去对抗大于 \(b[i]\) 的数，所以对于 \(b[i]\) 剩下 \((n - k - i)\) 种方案，方案数最小是 \(0\)。
其实就是个排列组合问题，别想太复杂了
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n;
scanf("%d", &n);
vector<int> a, b;
for (int i = 0; i < n; i++)
{
int t;
scanf("%d", &t);
a.push_back(t);
}
//a升序
sort(a.begin(), a.end());
for (int i = 0; i < n; i++)
{
int t;
scanf("%d", &t);
b.push_back(t);
}
//b降序
sort(b.rbegin(), b.rend());
//遍历b
ll ans = 1;
for (int i = 0; i < n; i++)
{
//找到第一个大于bi的ak
int t = n - (upper_bound(a.begin(), a.end(), b[i]) - a.begin()) - i; // n-k-i
ans = ans * max(t, 0) % mod;
}
printf(" %ld\n", ans);
}
}