首页 > 代码库 > HDU 6044 Limited Permutation 读入挂+组合数学

HDU 6044 Limited Permutation 读入挂+组合数学

2024-11-17 22:31:38   202人阅读

Limited Permutation

Problem Description
As to a permutation p1,p2,?,pn from 1 to n, it is uncomplicated for each 1≤i≤n to calculate (li,ri) meeting the condition that min(pL,pL+1,?,pR)=pi if and only if li≤L≤i≤R≤ri for each 1≤L≤R≤n.

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.
 
Input
The input contains multiple test cases.

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.
 
Output
For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1 and y denotes the answer of corresponding case.
 
Sample Input
3 1 1 3 1 3 3 5 1 2 2 4 5 5 2 5 5 5
 
Sample Output
Case #1: 2Case #2: 3
 

题解：

　　看懂题意

　　每个pi掌管 L ,R,题意是指超过这段范围就有比pi还要小的值

　　所有必然有一个pi 值掌管 1，n的，推出  必有  pj，pk分别 掌管 （1，i - 1）， （i+1,n） 

　　dfs下去计算方案

　　还有就是必须用读入挂才能过

#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;typedef unsigned long long ULL;const long long INF = 1e18+1LL;const double pi = acos(-1.0);const int N = 1e6+10, M = 1e3+20,inf = 2e9,mod = 1e9 + 7;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 int MOD = (int)1e9 + 7;int F[N], Finv[N], inv[N];//F是阶乘，Finv是逆元的阶乘void init(){    inv[1] = 1;    for(int i = 2; i < N; i ++){        inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;    }    F[0] = Finv[0] = 1;    for(int i = 1; i < N; i ++){        F[i] = F[i-1] * 1ll * i % MOD;        Finv[i] = Finv[i-1] * 1ll * inv[i] % MOD;    }}inline LL C(int n, int m){//comb(n, m)就是C(n, m)    if(m < 0 || m > n) return 0;    return F[n] * 1ll * Finv[n - m] % MOD * Finv[m] % MOD;}struct ss{    int l,r,id;    bool operator<(const ss& x) const{        if(l == x.l) return r > x.r;        else return l < x.l;    }}a[N];int now,ok;inline LL dfs(int ll,int rr) {    if(!ok) return 0;    if(ll > rr) return 1LL;    if(a[now].l != ll || a[now].r != rr) {        ok = 0;        return 0;    }    int ids = a[now++].id;    return dfs(ll,ids-1) * dfs(ids+1,rr) % mod * C(rr-ll,ids-ll) % mod;}int main() {    init();    int cas = 1,n;    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;        now = 1, ok = 1;        sort(a+1,a+n+1);        printf("Case #%d: %lld\n",cas++,dfs(1,n));    }    return 0;}

 

HDU 6044 Limited Permutation 读入挂+组合数学


联系
我们