首页 > 试题广场 >

魔法排列

[编程题]魔法排列
  • 热度指数：502 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解

众所周知，集合{1 2 3 … N}有N!种不同的排列，假设第i个排列为Pi且Pi,j是该排列的第j个数。将N个点放置在x轴上，第i个点的坐标为xi且所有点的坐标两两不同。对于每个排列（以Pi为例），可以将其视为对上述N个点的一种遍历顺序，即从第Pi,1个点出发，沿直线距离到达第Pi,2个点，再沿直线距离到达第Pi,3个点，以此类推，最后到达第Pi,N个点，将该路线的总长度定义为L(Pi)，那么所有N!种路线的总长度之和是多少，即L(P1)+L(P2)+L(P3)+...+L(PN!)的结果是多少？


输入描述:
第一行包含一个整数N，1≤N≤105。
第二行包含N个空格隔开的整数x1到xN，0≤x1<x2<x3<...<xN≤109。


输出描述:
输出L(P1)+L(P2)+L(P3)+...+L(PN!)对109+7取模后的结果。
示例1

输入

3
0 1 3

输出

24

说明

P1={1 2 3}，P2={1 3 2}，P3={2 1 3}，P4={2 3 1}，P5={3 1 2}，P6={3 2 1}；
L(P1)=3，L(P2)=5，L(P3)=4，L(P4)=5，L(P5)=4，L(P6)=3。
算法知识视频讲解
开通博客

暂无题解

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 2019 360集团 Java工程师
上传者：小小
难度：
6条回答 3318浏览

热门推荐

通过挑战的用户

相关试题

魔法排列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号