codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1827A.md (1582B)


      1 Source: https://codeforces.com/problemset/problem/1827/A
      2 
      3 A. Counting Orders
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given two arrays $a$ and $b$ each consisting of $n$ integers. All elements of $a$ are pairwise distinct.
     22 
     23 Find the number of ways to reorder $a$ such that $a_i \gt b_i$ for all $1 \le i \le n$, modulo $10^9 + 7$.
     24 
     25 Two ways of reordering are considered different if the resulting arrays are different.
     26 
     27 Input
     28 
     29 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.
     30 
     31 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$.
     32 
     33 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.
     34 
     35 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$.
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$.
     38 
     39 Output
     40 
     41 For each test case, output the number of ways to reorder array $a$ such that $a_i \gt b_i$ for all $1 \le i \le n$, modulo $10^9 + 7$.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 5
     49 
     50 6
     51 
     52 9 6 8 4 5 2
     53 
     54 4 1 5 6 3 1
     55 
     56 3
     57 
     58 4 3 2
     59 
     60 3 4 9
     61 
     62 1
     63 
     64 2
     65 
     66 1
     67 
     68 3
     69 
     70 2 3 4
     71 
     72 1 3 3
     73 
     74 12
     75 
     76 2 3 7 10 23 28 29 50 69 135 420 1000
     77 
     78 1 1 2 3 5 8 13 21 34 55 89 144
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 32
     85 0
     86 1
     87 0
     88 13824
     89 ```