重排列
题意
一个序列的重排列是指对这个序列中的元素进行若干次（包括0次）交换操作后得到的新序列 在本题中，序列中可能出现重复的数字，他们被视作不同的元素
例如，序列1 1的重排列有两种
现在有两个长度为 N 的非负整数序列 A 和 B，
问有多少种 A 的重排列满足对于所有的 1≤i≤N，有Ai≤Bi
由于答案可能很大，你只需要输出答案对1e9+7取模的结果
题解
对于每个位置的bi有多少A数组中的数(xi)小于等于bi
那么这个位置可以放的数有xi个
从xi最少的位置开始确定假设为x1 那么第二少的能放x2-1个 以此类推
最后是x1×(x2-1)×(x3-2)×…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| # include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[(int)1e5+5],b[(int)1e5+5];
const ll mod=(ll)1e9+7;
int main(){
int n;cin>>n;
vector<ll>de;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++)cin>>b[i];
sort(a,a+n);
for(int i=0;i<n;i++){
int pos=upper_bound(a,a+n,b[i])-a;
de.push_back(pos);
}
sort(de.begin(),de.end());
int len=de.size();
ll ans=1;
for(ll i=0;i<len;i++){
ans=((ans%mod)*(de[i]-i)%mod)%mod;
}
cout<<ans<<endl;
}
|