首页 > 试题广场 > 魔法排列
[编程题]魔法排列

众所周知,集合{1 2 3 … N}N!种不同的排列,假设第i个排列为PiPi,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。


       假设从N个点中的第一个点出发,可以到达其他的N-1个点,可以从上图看出,对于每一个片段经过的次数是不一样的,而将第一个点看做起点共有(N-1)!种情况,可以理解为将剩下的N-1个点进行排列组合,而N个点中每个点都可以作为起点,所以一共有N*(N-1)!=N!种情况,因此只要统计出以每一个点为出发点时各个片段经过的次数,然后再乘以各个片段的长度就得到了总的距离
part1 part2 part3 ... partN-1
1 N-1 N-2 N-3 ... 1
2 1 N-2 N-3 ... 1
3 1 2 N-3 ... 1
4 1 2 3 ... 1
... ... ... ... ... ...
N 1 2 3 ... N-1
上面的表格中行代表以哪个点为起点,列代表以当前点为起点每个片段经过的次数,总共有N行N-1列个数,对每一列求和然后乘以(N-1)!代表当前片段经过的总次数,设对第k∈[1,N−1]k∈[1,N−1]列求和,公式如下:

设第k段的距离为dkdk,则总的距离如下:

def factorial(n):                                      # 阶乘
    tmp = 1
    for i in range(1,n+1):
        tmp =  (tmp*i + (10**9 + 7)) % (10**9 + 7)     # 防止溢出
    return tmp
def result():
    n = int(input().strip('\n'))
    num_list = list(map(int, input().strip().split(' ')))
    sum = 0
    for i in range(1, n):
        tmp_distance = num_list[i] - num_list[i-1]
        sum += 2*i* (n - i) * tmp_distance
    sum *=  factorial(n-1)
    out = sum % (10**9 + 7)
    print(out)
result()



编辑于 2019-08-17 20:33:25 回复(0)
0/0头像 0/0
/* 思路
* 对于N个数中任意两个数a,b(a!=b)考虑先后顺序 , 有(a,b)及(b,a)两种情况
* 对于其中的(a,b)情况有,将其视为一个整体,插入剩下的(N-2)个数中,有(N-1)种插入方法,
*                    进而推出对N!个序列共有(N-1)*((N-2)!)=(N-1)!种(a,b)相邻情况。
* 同理对(b,a)也有(N-1)!种情况。
* 一共有C(N,2)对数对,对于(a,b)及(b,a)移动代价相同,所以只需求出C(N,2)对数的总代价P
* 最后  P * 2 * ((N-1)!) 即为最终解
* 当然考虑到 对(10^9+7) 取余
* */
import java.util.Arrays;
import java.util.Scanner;

public class Test6i {
public static void main(String[] args) {
Long yv = (long) (Math.pow(10, 9)+7);
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] number = new int[n];
for(int i=0;i<n;i++) {
number[i] = sc.nextInt();
}
Arrays.sort(number);//求总代价的过程,特殊操作,以减少时间复杂度
Long sum = 0L;
Long[] sumList = new Long[n];
for(int i=0;i<n;i++) {
if(i==0) {
sumList[i] = 0l;
}else {
sumList[i] = ((long)i*(long)(number[i]-number[i-1])+sumList[i-1]+yv)%yv;
}
}
for(int i=0;i<n;i++) {
sum = (sum + sumList[i] + yv)% yv;
}//总代价求取完毕。
Long muti = 2L;
for(int j=1;j<n;j++) {
muti = (muti * j + yv)%yv;
}
sum = sum * muti;
sum = (sum+yv) % yv;
System.out.println(sum);
}
}
编辑于 2019-08-14 23:00:27 回复(0)

这道题的思路就是排列组合,但因为计算中的数据过大,随时可能溢出,所以在每一个地方都需要考虑溢出的可能性。
举一个简单的例子讲解思路。
假如四个数分别是1 2 3 4 那么这四个数的排列组合一共有24种
1 2 3 4 - 1 2 4 3 - 1 3 2 4 - 1 3 4 2 - 1 4 2 3 - 1 4 3 2
2 1 3 4 - 2 1 4 3 - 2 3 1 4 - 2 3 4 1 - 2 4 1 3 - 2 4 3 1
3 1 2 4 - 3 1 4 2 - 3 2 1 4 - 3 2 4 1 - 3 4 1 2 - 3 4 2 1
4 1 2 3 - 4 1 3 2 - 4 2 1 3 - 4 2 3 1 - 4 3 1 2 - 4 3 2 1
分别统计1-2 · 2-1 · 1-3 ·3-1 · 1-4 · 4-1 · 2-3 · 3-2 · 2-4 · 4-2 · 3-4 · 4-3出现的次数。得出每一种情况都是6次
这里的6次是怎么来? 就是利用排列组合中的捆绑法原理
求1-2的次数,将1 2看成一个数捆绑在一起。那么1 2 3 4 四个数就变成了三个坑 三个坑中选一个放1 2,另外两个坑放3和4。
那么一共有C(3 1)A(2,2)=A(3,3)=6种。其他的方式也一样。
另外就是1-4和4-1是两种不同的组合。但是计算时只需要乘以2就可以了。
这道题用o(n^2)的时间复杂度通不过。所有只能进行优化。
例如1 2 3 4 以 2 3 4 开始的组合分别有(2,1)(3,1)(3,2) (4,1)(4,2)(4,3)(这些组合全都是前面一个数大于后面一个数)
这里以4结尾的数为例(4-1)+(4-2)+(4-3)=6=4*
3-(1+2+3) 这里1+2+3恰好是4出现之前所有已出现数之和。
所有我们用一个遍历temp表示前i-1项的和。那么算法的时间复杂度就可以简化成o(n)

import java.util.Scanner;

public class Main {

    static long mod=1000000007;
    //时间复杂度o(n^2)(这个时间复杂度不能通过测试 附上为了方便大家理解思路)
    public static int result(int arr[]) {

        long sum=0;
        long n=factorial(arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                int tmp=(arr[j]-arr[i])<<1;
                sum=(sum+tmp)%mod;
            }
        }
        sum=(sum*n)%mod;
        return (int)sum;
    }

    public static int factorial(int n) {
        long result=1;
        for (int i = 1; i <=n; i++) {
            result=(result*i)%mod;
        }
        return (int)result;
    }
    //时间复杂度(o(n))
    public static int SumOfDistence(int arr[]) {
        int n=factorial(arr.length-1);
        long sum=0;
        long tmp=0; 
        long a=0;
        for (int i = 1; i <arr.length; i++) {
            tmp=(tmp+arr[i-1])%mod;
            a=arr[i];
            a=a*i;
            //这里千万不能用sum=(sum+a[i]*i-tmp)%mod;
            //原因就是计算顺序中会先算a[i]*i,这两部分的计算结果是int,会导致溢出。所以只能增加一个long变量来进行计算
            sum=(sum+a-tmp)%mod;
        }

        sum=(sum<<1)%mod;
        sum=(sum*n)%mod;
        return (int) sum;
    }


    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int arr[] = new int[n];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = in.nextInt();
            }
            System.out.println(SumOfDistence(arr));
        }
    }
}
编辑于 2019-08-16 13:19:32 回复(12)
为什么L(p1) = 3   p1 = [1,2,3] 从1 到2 2到3  总距离不是2嘛  为啥是3
发表于 2019-08-14 23:02:08 回复(1)

热门推荐

通过挑战的用户