HDU-6044 Limited Permutation（计数）

传送门：点这里~

题意：对于有n个元素的全排列的合法性定义为：有n个区间，对于第i个区间[li,ri]有li<=i<=ri,对于任意1<=L<=i<=R<=n，当前仅当li<=L<=i<=R<=ri时P[i]=min(P[L],P[L+1],...,P[R])。现在给出序列和相应的区间，问区间是否合法？

题解：
首先要理解题意：当前仅当li<=L<=i<=R<=ri时P[i]=min(P[L],P[L+1],...,P[R])
因此对于P[i]一定有P[i]>P[li-1]且P[i]>P[ri+1]，进一步说区间[li,ri](除了[1,n])一定被某个区间[lj,rj]包含,且j=li-1或j=ri+1
即区间j可分成[lj,j-1]和[j+1,rj]

我们把n个区间按L升序R降序进行排序(这样得到的区间LR正是前序遍历的区间,区间由大到小)。得到的第1个区间一定要是[1,n](1比任何数都小)，否则不合法，输出0；设这个区间对应的是第i个数，因此区间可再分为[1,i-1]和[i+1,n],看是否有这2个区间，如果没有则不合法，输出0...直到区间不可再分。

现在再来考虑方法数：设f(i)为区间i内的方法数，u,v分别为左右子区间，i内一共有ri-li+1个数，除去中间一个，要从中选i-li个数放入左区间，剩下的放入右区间，因此答案为：f(i)=f(u)*f(v)*C(ri-li,i-li)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
namespace IO {
    const int MX = 4e7; //1e7占用内存11000kb
    char buf[MX]; int c, sz;
    void begin() {
        c = 0;
        sz = fread(buf, 1, MX, stdin);
    }
    inline bool read(int &t) {
        while(c < sz && buf[c] != '-' && (buf[c] < '0' || buf[c] > '9')) c++;
        if(c >= sz) return false;
        bool flag = 0; if(buf[c] == '-') flag = 1, c++;
        for(t = 0; c < sz && '0' <= buf[c] && buf[c] <= '9'; c++) t = t * 10 + buf[c] - '0';
        if(flag) t = -t;
        return true;
    }
}
const LL mod = 1e9 + 7;
const int MX = 1e6 + 5;
LL F[MX], invF[MX];
LL power(LL a, LL b) {
    LL ret = 1;
    while (b) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}
void init() {
    F[0] = 1;
    for (int i = 1; i < MX; i++) F[i] = F[i - 1] * i % mod;
    invF[MX - 1] = power(F[MX - 1], mod - 2);
    for (int i = MX - 2; i >= 0; i--) invF[i] = invF[i + 1] * (i + 1) % mod;
}
LL C(LL n, LL m) {
    LL ret = 1;
    while (n && m) {
        LL nn = n % mod, mm = m % mod;
        if (nn < mm) return 0;
        ret = ((ret * F[nn] % mod) * invF[mm] % mod) * invF[nn - mm] % mod;
        n /= mod, m /= mod;
    }
    return ret;
}
struct node {
    int l, r, id;
    bool operator<(const node& _A)const {
        if (l != _A.l) return l < _A.l;
        return r > _A.r;
    }
} a[MX];
int n;
int mark;  //是否有区间不合法
int rear;
LL dfs(int l, int r) {
    if (mark == 0) return 0;
    if (l > r) return 1;
    if (a[rear].l != l || a[rear].r != r) {
        mark = 0;
        return 0;
    }
    node now = a[rear++];
    LL ret = C(now.r - now.l, now.id - now.l) * dfs(now.l, now.id - 1) % mod;
    ret = (ret * dfs(now.id + 1, now.r)) % mod;
    return ret;
}
int main() {
    int cas = 0;
    init();
    //freopen("in.txt", "r", stdin);
    IO::begin();
    while (IO::read(n)) {
        for (int i = 1; i <= n; i++) IO::read(a[i].l);
        for (int i = 1; i <= n; i++) IO::read(a[i].r), a[i].id = i;
        sort(a + 1, a + n + 1);
        mark = rear = 1;
        printf("Case #%d: %lld\n", ++cas, dfs(1, n));
    }
    return 0;
}