Given the positive integers n, (li,ri) (1≤i≤n), you are asked to calculate the number of possible permutations p1,p2,⋯,pn from 1 to n, meeting the above condition.
The answer may be very large, so you only need to give the value of answer modulo 109+7.
For each test case:
The first line contains one positive integer n, satisfying 1≤n≤106.
The second line contains n positive integers l1,l2,⋯,ln, satisfying 1≤li≤i for each 1≤i≤n.
The third line contains n positive integers r1,r2,⋯,rn, satisfying i≤ri≤n for each 1≤i≤n.
It's guaranteed that the sum of n in all test cases is not larger than 3⋅106.
Warm Tips for C/C++: input data is so large (about 38 MiB) that we recommend to use fread() for buffering friendly.
size_t fread(void *buffer, size_t size, size_t count, FILE *stream); // reads an array of count elements, each one with a size of size bytes, from the stream and stores them in the block of memory specified by buffer; the total number of elements successfully read is returned.
现在给了n个(li,ri)求满足的排列有多少个。
思路：对于每个（li，ri）,a[li-1]<a[i]>a[ri+1] ,并且a[i]是a[li]~a[ri]的最小值，那么可以想到：对于区间(1,n)一定有一个最小值，所以一定有一个区间是(1,n)(用X表示)，那么这个最小值把区间X分成两部分U和V ，所以一定存在为U和V的区间，如果不存在，那么输出0，令f(X)表示符合条件的区间X的排列数，那么f(X)=f(U)*f(V)*C(U+V+1,U) 【注：C()表示组合数，U 表示区间U的大小】，所以我们只需要从区间(1,n)进行深搜即可，其中因为数据太大取模会用到逆元和组合数。
代码如下：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=1e6+;
const LL mod=1e9+;
LL fac[N], Inv[N];
/*int Scan()///输入外挂
{
int res=0,ch,flag=0;
if((ch=getchar())=='-')
flag=1;
else if(ch>='0'&&ch<='9')
res=ch-'0';
while((ch=getchar())>='0'&&ch<='9')
res=res*10+ch-'0';
return flag?-res:res;
}*/
namespace IO {
const int MX = 4e7; //1e7占用内存11000kb
char buf[MX]; int c, sz;
void begin() {
c = ;
sz = fread(buf, , MX, stdin);
}
inline bool read(int &t) {
while(c < sz && buf[c] != '-' && (buf[c] < '' || buf[c] > '')) c++;
if(c >= sz) return false;
bool flag = ; if(buf[c] == '-') flag = , c++;
for(t = ; c < sz && '' <= buf[c] && buf[c] <= ''; c++) t = t * + buf[c] - '';
if(flag) t = -t;
return true;
}
} void Init(){
fac[] = Inv[] = fac[] = Inv[] = ;
for(int i=; i<N; i++) fac[i] = fac[i-] * i % mod;
for(int i=; i<N; i++) Inv[i] = (mod - mod / i) * Inv[mod % i] % mod;
for(int i=; i<N; i++) Inv[i] = Inv[i] * Inv[i-] % mod;
}
LL C(LL n, LL m){
LL ans = fac[n] * Inv[m] % mod* Inv[n-m] %mod;
return ans;
}
int ii;
struct Node{
int l,r;
int id;
}a[N];
bool cmp(const Node s1,const Node s2)
{
if(s1.l==s2.l) return s1.r>s2.r;
return s1.l<s2.l;
}
LL dfs(int L,int R)
{
if(a[ii].l!=L || a[ii].r!=R) return ;
int m=a[ii++].id;
LL fL=,fR=;
if(L<=m-) fL=dfs(L,m-);
if(m+<=R) fR=dfs(m+,R);
LL c=C(R-L,m-L);
return fL*fR%mod*c%mod;
}
int main()
{
Init();
int n,Case=;
IO::begin();
while(IO::read(n))
{
for(int i=;i<=n;i++) IO::read(a[i].l);
for(int i=;i<=n;i++) IO::read(a[i].r), a[i].id = i;
sort(a+,a+n+,cmp);
ii=;
LL ans=dfs(,n);
printf("Case #%d: %lld\n",Case++,ans);
}
return ;
}