首页 > 试题广场 >

排列

[编程题]排列

n个二维点(a[i],b[i]), 其中1 ≤ i ≤ n，询问有多少种排列p（答案对1e9+7取模）使得执行以下伪代码后留下的点是k，即最后saved=k（其中1 ≤ k ≤ n）:

saved=p[1]
for x from 2 to n
    if a[p[x]] >= a[saved] and b[p[x]] >= b[saved]
        saved=p[x]

保证a[i]和b[i]分别为一个排列。

第一行一个整数n(n ≤ 100000)，接下来n行每行两个整数表示一个点。

n行每行一个整数表示留下的点为i的排列种数。

示例1

输入

0
4
2

算法知识视频讲解

__故人__

发表于 2020-09-21 20:30:07

分析我们对于一个节点考虑，如果有一个点两维都大于，那么这个节点肯定不可能作为结尾。因为考虑一下，如果排列先出现，那么这个两维都是单调不降的，所以不可能转移到，反之，如果先出现，它一定保持不住结尾，最后整个图构成了一个有向无环图，每一个节点可以等概率转移到后置节点。那么一个展开全文

C++工程师 golang工程师 2017 组合数学 iOS工程师分治安卓工程师树状数组运维工程师前端工程师算法工程师测试工程师 PHP工程师 c#工程师线段树美团测试开发工程师大数据开发工程师 Java工程师

来自：CodeM 2017美...

难度：

0条回答 7收藏 3274浏览

扫一扫，把题目装进口袋