Description
As we all know,God Qing is a very powerful ACMer. She very like junior sister apprentice,but in UESTC-ACM team,there is no junior sister apprentice,we can use a mathematical formula to express it.
But God Qing is a life winner , she has many beautiful girls,every girl has its BeautifulValue V ,and he want to take the most beautiful girl among all girls. For every girl,if God Qing chooses her,she can get a value called Life-Winner Point. We can use a mathematical formula to express it.
LifeWinnerPoint = HandsomeValue * BeautifulValue
When other people who come from UESTC-ACM team(such as Liao772002,Final-Pan,Final-Zhu and so on) know God Qing want to choose the most beautiful girl,they can't stand it! ,They also want a girl,for every person,he/she has its own HandsomeValue P. But God Qing wants to make her Life-Winner Point most,so she wants you to tell her there are how many ways can GodQing get the most Life-Winner Point.
In general. Thre are N competitors come from UESTC-ACM team(God Qing's ID is always 1) and N Girls, for every competitor,he/she has a HandsomeValue P[i] , for every girl , she has a BeatuifulValue V[i],every competitor can only choose a girl,and every girl can be only chose once. you should calculate there are how many ways that make GodQing get the most Life-Winner Point. (God Qing’s Life-Winner Point strictly greater than any other competitors).
Because the answer can be very large,you only need to print the answer modulo 10^9 + 7.
Input
Line 1: an integet N(the number of competitors and girls).
Line 2: N numbers p[i](the HandsomeValue of every competitor)
Line 3: N numbers v[i](the BeautifulValue of every girl).
1 <= N <= 100, 1 <= p[i] <= 10^6 , 1 <= v[i] <= 106.
Output
the number of ways that GodQing can get the most Life-Winner Point.
Sample Input
4
5 8 4 8
19 40 25 20 Sample Output
2
Hint
Valid assignment #1: (5,40), (8,19), (4,25), (8,20).
Valid assignment #2: (5,40), (8,20), (4,25), (8,19).
In assignment #1, the Life-Winner Point of God Qing is 5 x 40 = 200. The other three units have Life-Winner Point 8 x 19 = 152, 4 x 25 = 100, and 8 x 20 = 160. This is a valid assignment because the number 200 is strictly greater than each of the numbers 152, 100, and 160.
这题第一眼还以为是二分图匹配什么的，结果想了半天也没想法。
后来突然间就想到了，这其实就是个暴力枚举。
简单来说，先把除了godqing以为的人从大到小排，所有女生从小到大排，
对于godqing来说，枚举所有的女生和他组合，对于每个组合来说
统计最大的人能选的数量，然后在统计第二大的，在算进答案里的时候要减去被第一大的人选过的那1个
之后的同理，这样就能算出所有的组合了。
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<string>
#include<functional>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 2;
const int base = 1e9 + 7;
int T, n;
LL a[maxn], b[maxn], ans;
int main(){
//scanf("%d", &T);
while (~scanf("%d", &n))
{
for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
for (int i = 0; i < n; i++) scanf("%lld", &b[i]);
sort(a + 1, a + n, greater<int>()); sort(b, b + n);
ans = 0;
for (int i = 0; i < n; i++)
{
LL now = a[0] * b[i], res = 1, cnt = 0;
for (int j = 1, k = 0; j < n; j++)
{
while (k < n)
{
if (k == i) k++;
if (k < n&&a[j] * b[k] < now) { cnt++; k++; }
else break;
}
(res *= cnt--) %= base;
}
(ans += res) %= base;
}
printf("%lld\n", ans);
}
return 0;
}