Heros and Swords

Time Limit: 6000/3000MS (Java/Others) 

Memory Limit: 128000/64000KB (Java/Others)

   

Problem Description

There are n swords of different weights Wi and n heros of power Pi.

Your task is to find out how many ways the heros can carry the swords so that each hero carries exactly one sword.

Here are some rules:

(1) Every sword is carried by one hero and a hero cannot carry a sword whose weight is larger than his power.

(2) Two ways will be considered different if at least one hero carries a different sword.

Input

The first line of the input gives the number of test cases T(1 ≤ T ≤ 50).

Each case starts with a line containing an integer n (1 ≤ n ≤ 105) denoting the number of heros and swords.

The next line contains n space separated distinct integers denoting the weight of swords.

The next line contains n space separated distinct integers denoting the power for the heros.

The weights and the powers lie in the range [1, 109].

Output

For each case, output one line containing "Case #x: " followed by the number of ways those heros can carry the swords.

This number can be very big. So print the result modulo 1000 000 007.

Sample Input

351 2 3 4 51 2 3 4 521 32 232 3 46 3 5

Sample Output

Case #1: 1Case #2: 0Case #3: 4

一道贪心的题，在贪心中处理组合数用的2*n的时间复杂度，精妙

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
           
          
         
        
       
      
     

for(int i=0,j=0;i

版权声明：本文为博主原创文章，未经博主允许不得转载。