题意略。

思路：

I.对于整个区间a1,....,an，必然有一个区间[1,n]与之对应，因为a1,...,an是1,...,n的一个排列，所以在[1,n]中定然有一个最小的数字1，

如果最大的区间[l,r]长度比[1,n]小，那么我们可以知道在[l,r]之外的数字是依然大于1的，这使得1这个数字没有合法的地方可放。

II.起于1左端的区间不可能终于1的右端。

III.数字1左端的部分类似于整体，因为左端也类似地有一个最小的数字。

IV.要想知道整体的方案数有多少，假设可以由f(1,n)算出，那么f(1,n) = f(1,mid - 1) * f(mid + 1,r) * C(n - 1,mid - 1)。

V.这个题递归的顺序可以预先算出来。

 

#include
     
      //#pragma comment(linker,"/STACK:1024000000,1024000000")using namespace std;typedef long long LL;const LL mod = 1e9 + 7;const LL maxn = 1e6 + 5;inline bool scan_d(int& ret){    char c;int sgn;    if(c = getchar(),c == EOF) return 0;    while(c != '-' && (c < '0' || c > '9')) c = getchar();    sgn = (c == '-') ? -1 : 1;    ret = (c == '-') ? 0 : (c - '0');    while(c = getchar(),c >= '0' && c <= '9') ret = ret * 10 + (c - '0');    ret *= sgn;    return 1;} struct node{    int l,r,id;    node(int a = 0,int b = 0){        l = a,r = b;    }    bool operator<(const node& nd) const{        if(l != nd.l) return l < nd.l;        return r > nd.r;    }};int cnt;LL fac[maxn],inv[maxn];node store[maxn];bool flag;LL exgcd(LL a,LL b,LL& x,LL& y){    if(a == 0 && b == 0) return -1;    if(b == 0){        x = 1,y = 0;        return a;    }    LL d = exgcd(b,a % b,y,x);    y -= a / b * x;    return d;}LL rev(LL a,LL n){    LL x,y;    LL d = exgcd(a,n,x,y);    if(d == 1) return (x % n + n) % n;    else return -1;}void init(){    fac[0] = 1;    for(LL i = 1;i < maxn;++i) fac[i] = fac[i - 1] * i % mod;        inv[maxn - 1] = rev(fac[maxn - 1],mod);    for(LL i = maxn - 2;i >= 0;--i){        inv[i] = inv[i + 1] * (i + 1) % mod;        //printf("inv[%d] == %lld\n",i,inv[i]);    }}LL C(int n,int m){    return ((fac[n] * inv[m]) % mod) * inv[n - m] % mod;}LL dfs(int l,int r){    //printf("now l == %d r == %d\n",l,r);    if(flag) return 0;    if(l > r) return 1;        if(store[cnt].l != l || store[cnt].r != r){        flag = true;        return 0;    }     node cur = store[cnt++];    int mid = cur.id;    LL lft = 1,rht = 1,c = 1;    lft = dfs(l,mid - 1);    rht = dfs(mid + 1,r);    c = C(r - l,mid - l);    //printf("c == %lld\n",c);    //printf("---> %lld\n",(lft * rht % mod) * c % mod);    return (lft * rht % mod) * c % mod;}int main(){    int cas = 1,n;    init();    while(scan_d(n)){        flag = false;        cnt = 1;        for(int i = 1;i <= n;++i) scan_d(store[i].l);        for(int i = 1;i <= n;++i) scan_d(store[i].r),store[i].id = i;        sort(store + 1,store + n + 1);        LL ans = dfs(1,n);        printf("Case #%d: %lld\n",cas++,ans);    }    return 0;}