HDU 6044 Limited Permutation（2017多校）【计数 快速读入挂 线性逆元】

题目传送门：

 

题意：

对于有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])。

求排列的合法方案数；

 

解题思路：

大佬讲的很清楚了：

前期技能：

①快速读入挂

②线性求阶乘逆元

为什么这样排序之后 dfs 一定是合理的呢？

因为题目给出的是 N 个区间， 每个区间对应一个值，因为每个区间的合法定义都是唯一的，

也就是说序列中的每一个值其实对应一个区间，所以dfs区间是合理的，如果区间出现不合法的情况则说明无解。

 

AC code：