HDU 6044

题意略。

思路：

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<bits/stdc++.h>

//#pragma comment(linker,"/STACK:1024000000,1024000000")

using namespace std;

typedef long long LL;

const LL mod = 1e9 + ;

const LL maxn = 1e6 + ;

inline bool scan_d(int& ret){

    char c;int sgn;

    if(c = getchar(),c == EOF) return ;

    while(c != '-' && (c < '' || c > '')) c = getchar();

    sgn = (c == '-') ? - : ;

    ret = (c == '-') ?  : (c - '');

    while(c = getchar(),c >= '' && c <= '') ret = ret *  + (c - '');

    ret *= sgn;

    return ;

} 

struct node{

    int l,r,id;

    node(int a = ,int b = ){

        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 ==  && b == ) return -;

    if(b == ){

        x = ,y = ;

        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 == ) return (x % n + n) % n;

    else return -;

}

void init(){

    fac[] = ;

    for(LL i = ;i < maxn;++i) fac[i] = fac[i - ] * i % mod;

    inv[maxn - ] = rev(fac[maxn - ],mod);

    for(LL i = maxn - ;i >= ;--i){

        inv[i] = inv[i + ] * (i + ) % 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 ;

    if(l > r) return ;

    if(store[cnt].l != l || store[cnt].r != r){

        flag = true;

        return ;

    }

    node cur = store[cnt++];

    int mid = cur.id;

    LL lft = ,rht = ,c = ;

    lft = dfs(l,mid - );

    rht = dfs(mid + ,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 = ,n;

    init();

    while(scan_d(n)){

        flag = false;

        cnt = ;

        for(int i = ;i <= n;++i) scan_d(store[i].l);

        for(int i = ;i <= n;++i) scan_d(store[i].r),store[i].id = i;

        sort(store + ,store + n + );

        LL ans = dfs(,n);

        printf("Case #%d: %lld\n",cas++,ans);

    }

    return ;

}

巴特西

HDU 6044

最新文章

热门文章