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 ai>bi for all 1≤i≤n , modulo 109+7 . Two ways of reordering are considered different if the resulting arrays are different. Input Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104 ). The description of the test cases follows. The first line of each test case contains a single integer n (2≤n≤2⋅105 ) — the length of the array a and b . The second line of each test case contains n distinct integers a1 , a2 , … , an (1≤ai≤109 ) — the array a . It is guaranteed that all elements of a are pairwise distinct. The second line of each test case contains n integers b1 , b2 , … , bn (1≤bi≤109 ) — the array b . It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 . Output For each test case, output the number of ways to reorder array a such that ai>bi for all 1≤i≤n , modulo 109+7 .

题意简述：给定两个长度为n的数组a和b，每个数组都由n个不同的正整数组成。找出重新排列数组a的方式，使得对于所有1≤i≤n，ai>bi。如果得到的数组不同，则认为两种重新排列方式是不同的。求满足条件的方案数，对109+7取模。

思路：贪心+逆序对

首先，对数组a进行升序排序，对数组b进行降序排序。

然后，从a数组的末尾开始遍历，对于每个a[i]，找到b中第一个小于a[i]的数字b[j]，将a[i]插入到b[j]的前面，这样能够保证ai>bi，同时不改变其他数字的相对顺序。

最后，统计逆序对的个数即可，因为只有在构造过程中出现的逆序对才能够影响到方案数。

时间复杂度：O(nlogn)

参考代码：

相关问题

You are given two arrays a and b , both of length n . Your task is to count the number of pairs of integers (i,j) such that 1≤i<j≤n and ai⋅aj=bi+bj .

To solve this problem, we can first preprocess the array b to create a hash table that maps each value in b to its frequency. Then, for each pair of indices (i,j) such that i<j, we can check if ai⋅aj is equal to bi+bj by computing ai/bj and aj/bi and checking if they are equal. If they are equal, we can check if the values ai/bj and aj/bi are present in the hash table. If both values are present, we can increment our count by the product of their frequencies in the hash table.

The time complexity of this algorithm is O(n^2) due to the nested loops, but the constant factor is small due to the hash table lookups. Here is the Python code for the algorithm:

from collections import defaultdict

def count_pairs(a, b):
    n = len(a)
    freq = defaultdict(int)
    for x in b:
        freq[x] += 1
    count = 0
    for i in range(n):
        for j in range(i+1, n):
            if a[i]*a[j] == b[i]+b[j]:
                if b[i] != 0 and b[j] % b[i] == 0 and a[j] == (b[j] // b[i]) * a[i]:
                    x = b[i]
                    y = b[j] // b[i]
                    if x in freq and y in freq:
                        count += freq[x] * freq[y]
                if b[j] != 0 and b[i] % b[j] == 0 and a[i] == (b[i] // b[j]) * a[j]:
                    x = b[j]
                    y = b[i] // b[j]
                    if x in freq and y in freq:
                        count += freq[x] * freq[y]
    return count

Note that we need to check both possible orderings of ai and aj in case one of them is zero or the corresponding value in b is not present in the hash table.

You are given two arrays a and b,both of length n Your task is to count the number of pairs of integers (i,j) such that 1≤i<j≤n and ai⋅aj=bi+bj .

To count the number of pairs of integers (i,j) such that ai⋅aj=bi+bj, we can use a hash table to keep track of the count of each value in array a and b. Then, we can loop through all pairs of indices (i,j) and check if ai⋅aj=bi+bj. If it is true, we increment a counter.

Here is the code:

def count_pairs(a, b):
    n = len(a)
    count_a = {}
    count_b = {}
    for i in range(n):
        count_a[a[i]] = count_a.get(a[i], 0) + 1
        count_b[b[i]] = count_b.get(b[i], 0) + 1
        
    count = 0
    for i in range(n):
        for j in range(i+1, n):
            if a[i]*a[j] == b[i]+b[j]:
                count += 1
                
    return count

Note that this solution has a time complexity of O(n^2) because of the nested loops. However, we can make it more efficient by using a set to store all possible values of ai⋅aj and bi+bj, and then check if each product is in the set. This reduces the time complexity to O(n).