Problem:


Score : 600 points

Problem Statement

There are N slimes standing on a number line.
The i-th slime from the left is at position x_i.

It is guaruanteed that 1 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}.

Niwango will perform N-1 operations. The i-th operation consists of the following procedures:

Choose an integer k between 1 and N-i (inclusive) with equal probability.

Move the k-th slime from the left, to the position of the neighboring slime to the right.

Fuse the two slimes at the same position into one slime.

Find the total distance traveled by the slimes multiplied by (N-1)! (we can show that this value is an integer), modulo (10^{9}+7). If a slime is born by a fuse and that slime moves, we count it as just one slime.

Constraints

2 \leq N \leq 10^{5}

1 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}

x_i is an integer.

Subtasks

400 points will be awarded for passing the test cases satisfying N \leq 2000.

Input

Input is given from Standard Input in the following format:

N
x_1 x_2 \ldots x_N

Output

Print the answer.

Sample Input 1

3
1 2 3

Sample Output 1

5

With probability \frac{1}{2}, the leftmost slime is chosen in the first operation, in which case the total distance traveled is 2.

With probability \frac{1}{2}, the middle slime is chosen in the first operation, in which case the total distance traveled is 3.

The answer is the expected total distance traveled, 2.5, multiplied by 2!, which is 5.

Sample Input 2

12
161735902 211047202 430302156 450968417 628894325 707723857 731963982 822804784 880895728 923078537 971407775 982631932

Sample Output 2

750927044

Find the expected value multiplied by (N-1)!, modulo (10^9+7).



Sample input:
3
1 2 3


Sample output:
5

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = []
    r = 1
    for inv in mod_invs(max, mod):
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


def test2(X):
    ret = 0
    for xs in itertools.permutations(X[:-1]):
        print(xs)
        a = 0
        ss = list(X)
        for x in xs:
            ret += ss[ss.index(x) + 1] - x
            a += ss[ss.index(x) + 1] - x
            ss.remove(x)
            print(ss)
        print(a)
        print()
    print(ret % MOD)
    print()
    print()


N = int(sys.stdin.buffer.readline())
X = list(map(int, sys.stdin.buffer.readline().split()))

inv2 = pow(2, MOD - 2, MOD)


def div2(n):
    return n % MOD * inv2 % MOD


factorials = get_factorials(N + 10, MOD)
# test2(X)
# test(np.diff(X))

st = [0]
# 何回使うか
# わからんぽん
# https://oeis.org/A000254
for i in range(N + 1):
    st.append((i + 1) * st[-1] + factorials[i])

comb = Combination(max=N + 10, mod=MOD)
ans = 0
for i, d in enumerate(np.diff(X).tolist()):
    ans += d * st[i + 1] % MOD * comb.ncr(N, i + 1) % MOD * factorials[N - i - 1] % MOD
    ans %= MOD
ans *= pow(N, MOD - 2, MOD)
ans %= MOD
print(ans)

# for i in range(8):
#     N = i
#     counts = [0] * (N + 1)
#     for order in itertools.permutations(range(N)):
#         used = np.zeros(N)
#         a = 0
#         for i in order:
#             if used[:i].sum() == 0:
#                 a += 1
#                 used[i] = 1
#         counts[a] += 1
#     print(N)
#     print(counts)
#     print(counts * np.arange(N + 1))
#     print((counts * np.arange(N + 1)).sum())
#     print()

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
  
import sys
sys.setrecursionlimit(100000)
from math import factorial


mod = 10**9+7 #出力の制限
N = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
f=[0]*N
f[0]=1
for i in range(1,N):
  f[i]=(f[i-1]*i)%mod

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

n=int(input())
x=list(map(int,input().split()))
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    if j!=n-1:
      t = (x[j]-x[i])%mod
      o =( f[n-1-j+i-1]*f[j-i-1])%mod
      g = (cmb(n-1,j-i+1,mod)*o)%mod
      t = (t * g)%mod

      ans=(ans + t)%mod
    else:
      t = (x[j]-x[i])%mod
      o =( f[n-1-j+i]*f[j-i-1])%mod
      g = (cmb(n-1,j-i,mod)*o)%mod
      t = (t * g)%mod
      ans=(ans+t)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
  
import sys
sys.setrecursionlimit(100000)
from math import factorial


mod = 10**9+7 #出力の制限
N = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
f=[0]*N
f[0]=1
for i in range(1,N):
  f[i]=(f[i-1]*i)%mod

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

n=int(input())
x=list(map(int,input().split()))
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    if j!=n-1:
      ans=(ans+(((x[j]-x[i]))*cmb(n-1,j-i+1,mod)*f[n-1-j+i-1]*f[j-i-1])%mod)%mod
    else:
      ans=(ans+(((x[j]-x[i]))*cmb(n-1,j-i,mod)*f[n-1-j+i]*f[j-i-1])%mod)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import math
mod = 10**9 +7
N = int(input())
X = list(map(int, input().split()))

ans=0
for i in range(1,N):
    ans = (ans*i + (X[-1]-X[i-1])*math.factorial(i-1)) %mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
  
import sys
sys.setrecursionlimit(100000)
from math import factorial


mod = 10**9+7 #出力の制限
N = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
f=[0]*N
f[0]=1
for i in range(1,N):
  f[i]=(f[i-1]*i)%mod

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

n=int(input())
x=list(map(int,input().split()))
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    if j!=n-1:
      ans+=(((x[j]-x[i]))*cmb(n-1,j-i+1,mod)*f[n-1-j+i-1]*f[j-i-1]%mod)
    else:
      ans+=(((x[j]-x[i]))*cmb(n-1,j-i,mod)*f[n-1-j+i]*f[j-i-1]%mod)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
  
import sys
sys.setrecursionlimit(100000)
from math import factorial


mod = 10**9+7 #出力の制限
N = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
f=[0]*N
f[0]=1
for i in range(1,N):
  f[i]=(f[i-1])*i%mod

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

n=int(input())
x=list(map(int,input().split()))
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    if j!=n-1:
      ans+=(((x[j]-x[i]))*cmb(n-1,j-i+1,mod)*f[n-1-j+i-1]*f[j-i-1]%mod)
    else:
      ans+=(((x[j]-x[i]))*cmb(n-1,j-i,mod)*f[n-1-j+i]*f[j-i-1]%mod)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
  
import sys
sys.setrecursionlimit(100000)
from math import factorial
mod = 10**9+7 #出力の制限
N = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

n=int(input())
x=list(map(int,input().split()))
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    if j!=n-1:
      ans+=((x[j]-x[i]))*(cmb(n-1,j-i+1,mod)*(factorial(n-1-j+i-1)%mod)*(factorial(j-i-1)%mod))
    else:
      ans+=((x[j]-x[i]))*(cmb(n-1,j-i,mod)*(factorial(n-1-j+i)%mod)*(factorial(j-i-1)%mod))
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def factorial_cor(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

n=int(input())
x=list(map(int,input().split()))
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    if j!=n-1:
      ans+=((x[j]-x[i]))*(cmb(n-1,j-i+1,mod)*factorial_cor(n-1-j+i-1)%mod*factorial_cor(j-i-1)%mod)
    else:
      ans+=((x[j]-x[i]))*(cmb(n-1,j-i,mod)*factorial_cor(n-1-j+i)%mod*factorial_cor(j-i-1)%mod)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
N = int(input())
x = list(map(int, input().split()))
x.sort()
 
kaijo = [1]
for i in range(1, N):
    kaijo.append(kaijo[-1] * i)
 
ans = 0
for i in range(N - 1):
    ans = (ans * (i + 1) + (x[-1] - x[i]) * kaijo[i]) % MOD
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
n=int(input())
x=list(map(int,input().split()))
ans=0
for i in range(n):
    ans=(ans+(x[-1]-x[i])*(Fraction(1,i+1)))%(10**9+7)

for i in range(1,n):
    ans=ans*i%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from fractions import Fraction
n=int(input())
x=list(map(int,input().split()))
ans=0
for i in range(n):
    ans=(ans+(x[-1]-x[i])*(Fraction(1,i+1)))%(10**9+7)

ans=ans*math.factorial(n-1)%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

from fractions import Fraction
n=int(input())
x=list(map(int,input().split()))
l=[1]
for i in range(1,n-1):
    l.append(l[-1]+Fraction(1,i+1))
#print(l)

for i in range(n-1):
    l[i]=l[i]*(x[i+1]-x[i])%(10**9+7)

ans=sum(l)
ans=ans*math.factorial(n-1)%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
n=int(input())
x=list(map(int,input().split()))
l=[1]
for i in range(1,n-1):
    l.append(l[-1]+Fraction(1,i+1))
#print(l)

for i in range(n-1):
    l[i]=l[i]*(x[i+1]-x[i])%(10**9+7)

ans=sum(l)
for i in range(1,n):
    ans=ans*i%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
n=int(input())
x=list(map(int,input().split()))
l=[1]
for i in range(1,n-1):
    l.append(l[-1]+Fraction(1,i+1))
#print(l)

for i in range(n-1):
    l[i]*=x[i+1]-x[i]

ans=sum(l)
for i in range(1,n):
    ans=ans*i%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))
            
def main():
    N=I()
    X=LI()
    ans = ModInt(0)
    fact = ModInt(1)
    for i in range(1,N):
        fact*=i

    for i in range(N-1):
        dis = X[i+1]-X[i]
        for j in range(i+1):
            ans += dis * (fact/(i-j+1))
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import factorial


n = int(input())
x = list(map(int, input().split()))

kaijyo = factorial(n-1)
kaijyo_lis = [kaijyo//i for i in range(1, n)]
expect_sum = 0
kaijyo_sum = 0
for i in range(1, n):
    kaijyo_sum += kaijyo_lis[i-1]
    expect_sum += (x[i] - x[i-1]) * kaijyo_sum
    expect_sum %= (10**9+7)
print(expect_sum%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial


n = int(input())
x = list(map(int, input().split()))

kaijyo = factorial(n-1)
kaijyo_lis = [kaijyo//i for i in range(1, n)]
expect_sum = 0
kaijyo_sum = 0
for i in range(1, n):
    kaijyo_sum += kaijyo_lis[i-1]
    expect_sum += (x[i] - x[i-1]) * kaijyo_sum
print(expect_sum%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
x = list(map(int, input().split()))
ans = 0
mod = 10 ** 9 + 7
v = math.factorial(n - 1)


for i in range(1, n):
    w = (v//i)%mod
    ans += (x[n - 1] - x[i - 1]) * w
    ans %= mod

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import math

n=int(input())
x = list(map(int, input().split()))
ans=0
mod=10**9+7
v=math.factorial(n-1)

for i in range(1,n):
    ans+=(x[n-1]-x[i-1])*v//i
    ans%=mod

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import math
mod = 10 ** 9 + 7


n = int(input())
X = list(map(int, input().split()))

ans = 0
cum_pattern = []
pattern = 0
base = math.factorial(n-1)
for i in range(1, n):
    pattern += base // i
    pattern %= mod
    cum_pattern.append(pattern)


ans = 0
for i in range(n-1):
    dist = X[i+1] - X[i]
    ans += cum_pattern[i] * dist % mod
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from fractions import Fraction

def main(): 
    N = int(input())
    x = [int(i) for i in input().split()]

    MOD = 10**9+7

    answer = 0
    frac = 0
    for i in range(N-1):
        frac += Fraction(1,i+1)
        dist = (x[i+1] - x[i]) % MOD
        answer = (answer + dist * frac) % MOD
    for i in range(1,N):
        answer = (answer * i) % MOD

    print(int(answer))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from fractions import Fraction

def main(): 
    N = int(input())
    x = [int(i) for i in input().split()]

    MOD = 10**9+7

    frac = [""] * (N-1)
    for i in range(N-1):
        if i == 0:
            frac[i] = Fraction(1,i+1)
        else:
            frac[i] = (frac[i-1] + Fraction(1,i+1))

    answer = 0
    for i in range(N-1):
        dist = (x[i+1] - x[i]) % MOD
        answer = (answer + dist * frac[i]) % MOD
    for i in range(1,N):
        answer = (answer * i) % MOD

    print(int(answer))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import sys 
input = sys.stdin.readline
N = int(input())
x = list(map(int,input().split()))

d = [0]*(N-1)
for i in range(N-1):
    d[i] = x[i+1]-x[i]
    d[i] %= 10**9+7


kaijou = 1
for i in range(1,N):
    kaijou *= i%(10**9+7)

#kaijou = math.factorial(N-1)%(10**9+7)
ans=0
x=0
k=10**9+5

def pow_r(x, n):
    """
    O(log n)
    """
    x %= (k+2)
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2, n // 2)%(k+2)
    else:  # standard case ② n is odd
        return (x * pow_r(x ** 2, (n - 1) // 2))%(k+2)

for i in range(N-1):
    #(i+1)**(10**9+5)を計算してyへ
    y = pow_r(i+1,k) 
    #x+= kaijou//(i+1))%(10**9+7)
    x += (kaijou*y)%(10**9+7)
    ans+= d[i]*x

print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math
import sys 
input = sys.stdin.readline
N = int(input())
x = list(map(int,input().split()))

d = [0]*(N-1)
for i in range(N-1):
    d[i] = x[i+1]-x[i]
    d[i] %= 10**9+7


kaijou = 1
for i in range(1,N):
    kaijou *= i%(10**9+7)

kaijou = math.factorial(N-1)%(10**9+7)
ans=0
x=0
k=10**9+5

def pow_r(x, n):
    """
    O(log n)
    """
    x %= (k+2)
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2, n // 2)%(k+2)
    else:  # standard case ② n is odd
        return (x * pow_r(x ** 2, (n - 1) // 2))%(k+2)

for i in range(N-1):
    #(i+1)**(10**9+5)を計算してyへ
    y = pow_r(i+1,k) 
    #x+= kaijou//(i+1))%(10**9+7)
    x += (kaijou*y)%(10**9+7)
    ans+= d[i]*x

print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = list(map(int,input().split()))
ans = 0
mod = 10**9+7
l=[1]*(N+1)
a=1
for i in range(2,N+1):
  a*=i
  a%=mod
  l[i]=a
x=X[-1]
for i in range(N-1):
  for j in range(i+1,N-1):
    a = j-i-1
    ans += (X[j]-X[i])*(l[a])%mod*l[N-1]%mod*pow(l[a+2],mod-2,mod)%mod
    
for k,y in enumerate(X[:N-1:]):
  a = N-k-2
  ans+=(x-y)*l[a]%mod*l[N-1]%mod*pow(l[a+1],mod-2,mod)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = list(map(int,input().split()))
ans = 0
mod = 10**9+7
l=[1]*(N+1)
a=1
for i in range(2,N+1):
  a*=i
  a%=mod
  l[i]=a
x=X[-1]
for i in range(N-1):
  for j in range(i+1,N-1):
    a = j-i-1
    ans += (X[j]-X[i])*(l[a])%mod*l[N-1]%mod*pow(l[a+2],mod-2,mod)%mod
    
for k,y in enumerate(X[:N-1:]):
  a = N-k-2
  ans+=(x-y)*l[a]%mod*l[N-1]%mod*pow(l[a+1],mod-2,mod)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/dwacon6th-prelims/submissions/9425560
# 部分点解法

def main():
    from functools import reduce

    MOD = 10 ** 9 + 7

    n = int(input())
    *x, = map(int, input().split())

    fact = [1]
    for i in range(1, n + 1):
        fact.append(fact[-1] * i)

    dist_to_r_edge = [x[-1] - x_ for x_ in x[:-1]]

    ret = reduce(
        lambda a, b: (a + b) % MOD,
        (
            d * pow(i, MOD - 2, MOD)
            for i, d in enumerate(dist_to_r_edge, 1)
        )
    )
    print(ret * fact[n - 1] % MOD)


if __name__ == '__main__':
    main()

# ret = 0
# for i, d in enumerate(dist_to_r_edge, 1):
#     ret = (ret + d * pow(i, MOD - 2, MOD)) % MOD
# print(ret * fact[n - 1] % MOD)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
x = list(map(int,input().split()))
  
ans = 0
mod = 10**9 + 7
fact = math.factorial(N-1)
n = fact % mod
tmp = n
for i in range(N-1):
  ans = ans + (x[i+1] - x[i]) * n
  #ans = ans % mod
  n = (n % mod) + ((fact // (i+2)) % mod)
  #n = n % mod

  
ans = ans % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = list(map(int, input().split()))

kaijyo = 1
for i in range(1, n):
    kaijyo *= i
kaijyo_lis = [kaijyo//i for i in range(1, n)]
expect_sum = 0
kaijyo_sum = 0
for i in range(1, n):
    kaijyo_sum += kaijyo_lis[i-1]
    expect_sum += (x[i] - x[i-1]) * kaijyo_sum
print(expect_sum%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = list(map(int, input().split()))

kaijyo = 1
for i in range(1, n):
    kaijyo *= i
kaijyo_lis = [kaijyo for i in range(n-1)]
for i in range(1, n):
    kaijyo_lis[i-1] = kaijyo_lis[i-1] // i
expect_sum = 0
kaijyo_sum = 0
for i in range(1, n):
    kaijyo_sum += kaijyo_lis[i-1]
    expect_sum += (x[i] - x[i-1]) * kaijyo_sum
print(expect_sum%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = list(map(int, input().split()))

kaijyo = 1
for i in range(1, n):
    kaijyo *= i
kaijyo_lis = []
for i in range(1, n):
    kaijyo_lis.append(kaijyo//i)
expect_sum = 0
kaijyo_sum = 0
for i in range(1, n):
    kaijyo_sum += kaijyo_lis[i-1]
    expect_sum += (x[i] - x[i-1]) * kaijyo_sum
print(expect_sum%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = list(map(int, input().split()))
dis = []
for i in range(n-1):
    dis.append(x[i+1] - x[i])
kaijyo = 1
for i in range(1, n):
    kaijyo *= i
kaijyo_lis = []
for i in range(1, n):
    kaijyo_lis.append(kaijyo//i)
expect_sum = 0
kaijyo_sum = 0
for i in range(1, n):
    kaijyo_sum += kaijyo_lis[i-1]
    expect_sum += dis[i-1] * kaijyo_sum
print(expect_sum%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = list(map(int, input().split()))
dis = []
for i in range(n-1):
    dis.append(x[i+1] - x[i])
kaijyo = 1
for i in range(1, n):
    kaijyo *= i
kaijyo_lis = []
for i in range(1, n):
    kaijyo_lis.append(kaijyo//i)
expect_sum = 0
for i in range(1, n):
    expect_sum += (dis[i-1] * sum(kaijyo_lis[0:i]))
print(expect_sum%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
x = list(map(int,input().split()))
  
ans = 0
mod = 10**9 + 7
fact = math.factorial(N-1)
n = 0
for i in range(N-1):
  n = n + (fact // (i+1))
  n = n % mod
  ans = ans + (x[i+1] - x[i]) * n
  ans = ans % mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,*X=map(int,open(0).read().split());M,g,r,h,i=10**9+7,1,0,[1],N;exec("i-=1;h+=[h[-1]*i%M];"*N+"r,g=(r+g*h[N-2-i]*(X[-1]-X[i]))%M,g*-~i%M;i+=1;"*N);print(r)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
n = int(input())
l = list(map(int, input().split()))

d = 0
ans = 0

for i in range(1, n):
  f = 1 if i == 1 else f * (i-1) % mod
  d = d * i + f
  ans = (ans * i + (l[i] - l[i-1]) * d) % mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
x = list(map(int,input().split()))
  
ans = 0
mod = 10**9 + 7
fact = math.factorial(N-1)
n = 0
for i in range(N-1):
  n = n + (fact // (i+1))
  n = n % mod
  ans = ans + (x[i+1] - x[i]) * n

ans = ans % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = list(map(int, input().split()))
mod = 10**9 + 7
X = []
for i in range(n - 1):
    X.append(x[i + 1] - x[i])
l, left = 1, [1]
for i in range(1, n - 1):
    l *= i
    l %= mod
    left.append(l)
r, right = 1, [1]
for i in range(n - 1, 1, -1):
    r *= i % mod
    right.append(r)
right.reverse()
f, flst = 0, []

for i, j in zip(left, right):
    f += i * j % mod
    f %= mod
    flst.append(f)
s = 0
for i, j in zip(X, flst):
    s += i * j % mod
print(s % mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
n = int(input())
lx = list(map(int, input().split()))

from math import factorial as kj

d = 0
ans = 0

for i in range(1, n):
  d = (d * i + kj(i-1)) % mod
  ans = (ans * i + (lx[i] - lx[i-1]) * d) % mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = list(map(int, input().split()))
mod = 10**9 + 7
X = []
for i in range(n - 1):
    X.append(x[i + 1] - x[i])
l, left = 1, [1]
for i in range(1, n - 1):
    l = l * i % mod
    left.append(l)
r, right = 1, [1]
for i in range(n - 1, 1, -1):
    r *= i % mod
    right.append(r)
right.reverse()
f, flst = 0, []

for i, j in zip(left, right):
    f += (i * j) % mod
    flst.append(f)
s = 0
for i, j in zip(X, flst):
    s += i * j % mod
print(s % mod)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=list(map(int, input().split()))
mod = 10**9+7
last=x[-1]
X=[]
for i in x[:-1]:
  X.append(last-i)
l=1
left=[1]
for i in range(1, n-1):
  l=l*i%mod
  left.append(l)
r=1
right=[1]
for i in range(n-1, 1, -1):
  r*=i%mod
  right.append(r)
right.reverse()
flst=[]
for i,j in zip(left,right):
  flst.append((i*j)%mod)
s=0
for i,j in zip(X,flst):
  s+=i*j%mod
print(s%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read

n,*X=map(int,read().split())
mod = 10**9+7
last=X[-1]
X=[last-i for i in X[:-1]]
l=1
left=[1]
for i in range(1, n-1):
  l=l*i%mod
  left.append(l)
r=1
right=[1]
for i in range(n-1, 1, -1):
  r*=i%mod
  right.append(r)
right.reverse()
flst=[]
for i,j in zip(left,right):
  flst.append(i*j%mod)
s=0
for i,j in zip(X,flst):
  s+=i*j%mod
print(s%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read

n,*X=map(int,read().split())
mod = 10**9+7
last=X[-1]
X=[last-i for i in X[:-1]]
l=1
left=[1]
for i in range(1, n-1):
  l=l*i%mod
  left.append(l)
r=1
right=[1]
for i in range(n-1, 1, -1):
  r*=i%mod
  right.append(r)
right.reverse()
flst=[i*j%mod for i,j in zip(left,right)]
s = sum(i*j%mod for i,j in zip(X,flst))
print(s%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read

n,*X=map(int,read().split())
mod = 10**9+7
last=X[-1]
X=[last-i for i in X[:-1]]
l=1
left=[1]
for i in range(1, n-1):
  l=l*i
  left.append(l)
r=1
right=[1]
for i in range(n-1, 1, -1):
  r*=i
  right.append(r)
right.reverse()
flst=[i*j for i,j in zip(left,right)]
s = sum(i*j%mod for i,j in zip(X,flst))
print(s%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
n = int(input())
lx = list(map(int, input().split()))

from math import factorial as kj

d = 0
ans = 0

for i in range(1, n):
  d += kj(n-1) // i % mod
  ans = (ans + (lx[i] - lx[i-1]) * d) % mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 10 ** 9 + 7
N = int(input())
x = list(map(int, input().split()))
x.sort()
x_arr = np.array(x)
x_diff = np.diff(x_arr)

a = np.zeros(N - 1, dtype=int)
a[0] += 1
for i in range(1, N - 1):
    a[i] = a[0]
    a[:i] = a[:i] * (i + 1) % MOD
a = np.cumsum(a) % MOD

print(np.dot(a, x_diff) % MOD)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
n = int(input())
lx = list(map(int, input().split()))

from math import factorial as kj

d = 0
lk = [0] * n

for i in range(1, n):
  d += kj(n-1) // i % mod
  lk[i] = (lx[i] - lx[i-1]) * d % mod

print(sum(lk) % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

mod = 10**9+7


def main():
    N = int(input())
    X = list(map(int, input().split()))
    D = [0 for i in range(N)]

    for i in range(N-1):
        D[i] = X[i+1] - X[i]

    import math
    n = math.factorial(N-1)

    ans = 0
    r = 0
    for i in range(1, N):
        r += n // i
        ans += D[i-1] * r
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
n = int(input())
lx = list(map(int, input().split()))

from math import factorial as kj

d = 0
lk = [0] * n

for i in range(1, n):
  d += kj(n-1) // i
  lk[i] = (lx[i] - lx[i-1]) * d

print(sum(lk) % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read

sys.setrecursionlimit(100002)
def myfact(n):
    if n < 2:
        return 1
    else:
        return n * myfact(n - 1)
n,*X=map(int,read().split())
mod = 10**9+7
last=X[-1]
X=[last-i for i in X[:-1]]

f=myfact(n-1)
flst=[f//i%mod for i in range(1,n)]
s = sum(i*j%mod for i,j in zip(X,flst))
print(s%mod)

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
x = list(map(int, input().split()))
d = [x[i+1] - x[i] for i in range(n - 1)]

def fact(m):
  return m * fact(m-1) % 1000000007 if m != 1 else 1
 
fact_n_1 = math.factorial(n-1)

e = [None] * (n-1)
for i in range(n-1):
  if i == 0:
    e[i] = fact_n_1
  else:
    e[i] = (e[i - 1] + fact_n_1 // (i + 1)) % 1000000007

print(sum(e_i * d_i % 1000000007
          for i, (d_i, e_i) 
          in enumerate(zip(d, e))) % 1000000007 )

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
x = list(map(int,input().split()))

diff = []

#for i in range(N-1):
#  d = x[i+1] - x[i]
#  diff.append(d)
  
ans = 0
fact = math.factorial(N-1)
n = 0
for i in range(N-1):
  d = x[i+1] - x[i]
  #diff.append(d)
  n = n + (fact // (i+1))
  ans = ans + d * n

mod = ans % (10**9 + 7)
print(int(mod))

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
x = list(map(int,input().split()))

diff = []

for i in range(N-1):
  d = x[i+1] - x[i]
  diff.append(d)
  
ans = 0
fact = math.factorial(N-1)
n = 0
for i in range(N-1):
  n = n + (fact // (i+1))
  ans = ans + diff[i] * n

mod = ans % (10**9 + 7)
print(int(mod))