D-重排列

一个序列的重排列是指对这个序列中的元素进行若干次(包括0次)交换操作后得到的新序列

在本题中,序列中可能出现重复的数字,他们被视作不同的元素

例如,序列1 1的重排列有两种

现在有两个长度为 N 的非负整数序列 A 和 B,问有多少种 A 的重排列满足对于所有的 1 ≤ i ≤ N,有Ai ≤ Bi

由于答案可能很大,你只需要输出答案对1e9+7取模的结果

输入描述

输入第一行,包含一个正整数 N

接下来一行,N 个非负整数表示序列 A

再接下来一行,N 个非负整数表示序列 B

1 ≤ N ≤ 105

0 ≤ Ai,Bi ≤109

输出描述

一行一个整数,表示答案

示例:

输入

4
1 1 2 3
1 2 3 4

输出

8

题解

题意就是说数组A所以重排列中,有多少个满足所以的 i (1 ≤ i ≤ N),有Ai ≤ Bi

这道题可以从大到小贪心选择数组A中的数,查找数组B中有多少个数是大于等于Ai的。

例如样例中的数据,

  • [ ] A从3开始,B中有2个值大于等于3,说明3有2个位置可以选择。
  • [ ] 然后查找2,B中有3个值大于等于2,说明2有3个位置可以选择。但是上一步已经占了一个位置,所以需要减掉1,也就是有2个位置可以选择
  • [ ] 接着查找第一个1,B中4个值大于等于1,减掉前两个数占的位置,第一个1只有2个位置可以选择
  • [ ] 最后查找第二个1,B中4个值大于等于1,减掉前三个数占的位置,第二个1只剩1个位置可以选择
  • [ ] 最后 2 2 2 * 1 就是要求的结果了

因为需要查找数组B,可以将数组B排序后用二分来查找。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5+7;
const ll mod = 1e9+7;
ll a[N],b[N];
int cmp(ll a,ll b)
{
    return a>b;
}
int main()
{
    ll n;
    cin>>n;
    for(int i=0; i<n; i++)  cin>>a[i];
    for(int j=0; j<n; j++)  cin>>b[j];

    sort(a,a+n,cmp);//a数组从大到小排序
    sort(b,b+n);

    ll ans = 1;
    for(ll i=0; i<n; i++)
    {
        ll k = n-(lower_bound(b,b+n,a[i]) - b); //二分查找
        //k存的是b数组中大于等于a[i]的数量,k-i即为可以选择的位置数量
        ans=ans*(k-i>0?k-i:0)%mod;//如果k<=i 说明当前a[i]没有位置可以选择
    }
    cout<<ans%mod<<endl;
    return 0;
}

自己二分写的不熟,比赛中一直wa,搞不懂哪里错了,最后用了STL里的二分函数,还是wa。

然后无意的把ans*=(k-i>0?k-i:0)%mod 改成了 ans=ans*(k-i>0?k-i:0)%mod 一下就AC了,运算符优先级的问题,百度了一下看到 *=的优先级要比 % 优先级小得多,下次不会再偷懒了。


一个好奇的人