魔法排列

这道题的思路就是排列组合，但因为计算中的数据过大，随时可能溢出，所以在每一个地方都需要考虑溢出的可能性。
举一个简单的例子讲解思路。
假如四个数分别是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));
        }
    }
}

import sys, math
if __name__ == '__main__':
    N, res, total = int(sys.stdin.readline().strip()), 0, 0
    for index, num in enumerate(list(map(int, sys.stdin.readline().split()))):
        res, total = res + num * index - total, total + num
    print(res*2*math.factorial(N-1)%1000000007)