HDU 6044 Limited Permutation （组合数+逆元）

HDU 6044 Limited Permutation （组合数+逆元）

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 10^9+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⋅10^6.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

31 1 31 3 351 2 2 4 55 2 5 5 5

Sample Output

Case #1: 2Case #2: 3

题意

给出 n 组 [li,ri] 代表 pi

思路

对于区间 [li,ri] ，我们可以将其分为 [li,i−1] 和 [i+1,ri]

于是对整个区间 [1,n] 进行递归分治搜索，每一个区间可贡献的值为其两个子区间贡献之积乘以 Ci−LR−L

PS：因为我们要在区间 [L,R] 中选取 i−L 个数放置在 i 的左边，其中区间 [L,R] 除去 i 后剩 R−L 个数，所以为 Ci−LR−L

AC 代码

#include#include#include#include#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。