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
from fractions import gcd

def main():
    N = int(input())
    a = list(map(int, input().split()))
    standard = a[-1] - a[0]
    all_pattern = list(itertools.permutations([i for i in range(1,N)]))
    #print(all_pattern)
    total = standard * len(all_pattern)
    for i, node in enumerate(all_pattern):
        for p, num in enumerate(node):
            if p >= 0 and num-1 in node[0:num-1]:
                total += a[num] -a[num-1]
                
    print(int(total%(10e9+7)))
 
main()

Submission status: Time Limit Exceeded

Solution code:
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]

kaijou = 1
for i in range(1,N):
    kaijou *= i

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

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
import fractions

mod = 10 ** 9 + 7

N = int(input())

x = list(map(int, input().split()))
for i in range(N):
    x[i] %= mod

x = x[::-1]
x_head = x.pop(0)
ans = 0

for i in itertools.permutations(x):
    ar = list(i)
    ar.insert(0, x_head)
    for j in range(N-1):
        ans += abs(ar[j] - ar[j+1])
print(ans)

Submission status: Time Limit Exceeded

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

import sys
from math import factorial

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD

N = INT()
A = LIST()
B = [0] + [A[i+1] - A[i] for i in range(N-1)]

add = factorial(N-1) % MOD
cnt = [0] * N
for i in range(1, N):
    cnt[i] = round(cnt[i-1] + add)
    cnt[i] %= MOD
    add *= fermat(i , (i+1), MOD)

ans = 0
for i in range(1, N):
    ans += B[i] * cnt[i]
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list( map(int, input().split() ) )
kai = 1
M = 10**9+7
result = 0
for i in range(1,N):
    kai *= i

for i in range(N-1):
    result += ((kai//(i+1))%M) * (a[N-1] - a[i])

print( result%M )

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = list(map(int, input().split()))
r = 10 ** 9 + 7
a = [1]
p = 1
for i in range(1, n - 1):
    p *= i
    q = p + a[0] * (i + 1)
    a = [q] + a

ans = (x[n - 1] - x[n - 2]) * a[0]
ans %= r
k = n - 1
for i in range(2, n):
    ans += (x[n - i] - x[n - i - 1]) * a[i - 1] * k
    ans %= r
    k *= n - i

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True

ans=0


n=I()
x=LI()
p=permutations(range(n-1))
cm=Comb(n+2)

StrN=[0]*(n+1)
StrN[1]=1
def St(n):
    if n==1:
        return 1
    if StrN[n]!=0:
        return StrN[n]
    else:
        #a(n+1)=(n+1)*a(n)+n!.
        StrN[n]=(n)*StrN[n-1]+cm.fac[n-1]
        return StrN[n]



for i in range(1,n):
    St(i)

St(n-1)

Pat=[0]*(n+1)
for i in range(n):
    Pat[i]=StrN[i]*cm.fac[n-1]*cm.inv[i]%mo
#show('Pat',Pat)
#show('St',StrN)

for i in range(n-1):
    ans+=(x[i+1]-x[i])*Pat[i+1]
    ans%=mo

print(ans%mo)
#show(SSS)

Submission status: Time Limit Exceeded

Solution code:
import itertools


N = int(input())

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

mod = 10 ** 9 + 7


ans = 0
t = [1]
u = [1]

for i in range(N):

    i += 1
    t.append(t[-1] * i % mod)

for i in range(N-1):
    u.append(u[-1] * (N-1-i))
    
#print (t)
#print (u)
u.reverse()


now = 0
for i in range(N-1):

    now += u[i+1] * t[i]
    now %= mod
    ans += now * (x[i+1] - x[i])
    ans %= mod
    #print (i,ans/6)

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
n = int(input())
*x, = map(int, input().split())

p = 1/(n-1)
ev = 0

for v in itertools.permutations(x[0:n-1], n-1):
    v = list(v)
    v.append(3)
    m = 0
    for i in range(len(v)-1):
        m += abs(v[i]-v[i+1])

    ev += p*m

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

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
n = int(input())
x = [int(x) for x in input().split()]
x = x[::-1]

dp = [0 for _ in range(n)]
dp[1] = x[0]-x[1]

xx = [0]
for i in range(n):
    xx.append((xx[-1]+x[i]) % mod)

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


def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    # a*x+y*mod = 1
    return (mod+x % mod) % mod


for i in range(2, n):
    dp[i] += i*dp[i-1] + (x[0]-x[i])*fact[i-1]
    dp[i] %= mod
    for k in range(1, i):
        s = inv((i-k+1)*(i-k), mod)
        dp[i] += (x[k]-x[i]) * fact[i] * s
        dp[i] %= mod

print(dp[n-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def main():
    n = inp()
    x = inpl()
    ans = 0
    d = []
    for i in range(n-1):
        d.append(x[i+1]-x[i])
    y = 1
    for i in range(1,n):
        y = (y*i)%mod
    for i in range(n-1):
        a = 1
        ans = (ans + d[i]*y)%mod
        for j in range(1,n):
            if i+2 == j:
                continue
            else:
                a = (a*j) % mod
        y = (y+a)%mod
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np
# import fractions
import itertools

n = int(input())

l = input().split()

for i in range(n):
    l[i] = int(l[i])

new_l = [l[n-1]-i for i in l]
# print(new_l)

new_l.pop()

ruiseki = np.cumsum(new_l)
# print(ruiseki)
allSum = sum(ruiseki)
# ans = allSum/fractions.factorial(n)
factorial = len(list(itertools.permutations(new_l)))
# print(factorial)

ans = int(allSum/(n-1) * factorial)
print(ans % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

cnt = 0
slimes = [i for i in range(n)]
for i in itertools.permutations(slimes[:n-1], n-1):
  s = [i for i in range(n)]
  for index in i:
    current = s.index(index)
    next = s[current + 1]
    s.pop(current)
    cnt += x[next] - x[index]
    cnt %= (10**9 + 7)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools

N = int(input())
x = [int(i) for i in input().split(' ')]

factorial = math.factorial(N-1)
sumexp = 0

linelist = list(range(N-1))

patterns = [i for i in itertools.permutations(linelist, N-1)]
for pattern in patterns:
    expvalue = 0
    valexists = [True] * N
    for i in pattern:
        valcheck = i + 1
        expvalue += x[valcheck] - x[i]
        valexists[i] = False
        while valexists[valcheck] == False:
            valcheck += 1
            expvalue += x[valcheck] - x[valcheck - 1]
    sumexp += expvalue

answer = (sumexp * factorial // len(patterns)) % (10 ** 9 + 7)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

dict = {}
for i in itertools.combinations(range(N), 2):
    dict[i] = X[i[1]] - X[i[0]]

count = 0
for i in itertools.permutations(range(N-1)):
    for idx, j in enumerate(i):
        k = 1
        while j+k in i[:idx]:
            k += 1
        count += dict[(j, j+k)]
print(count % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math
import random
from operator import itemgetter
import re
import sys
from itertools import accumulate
from collections import defaultdict
from collections import deque
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import functools
N = int(input())
x = [int(i) for i in input().split()]
mod = 10**9+7
start = 1
all_dis = 0
for i in range(N-1):
    far = x[i+1]-x[i]
    all_dis += far*start*math.factorial(N-1)//math.factorial(i+1)
    start = (start*(i+2)+math.factorial(i+1))%mod
    all_dis %= mod
print(all_dis)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
X = rl()
MOD = 10 ** 9 + 7
limit = math.factorial(N-1)
last = X[-1]
X = [last - x for x in X] #最後までの距離
answer = 0
for i in range(1, N):
    answer += X[i-1] * (limit // i)%MOD
    answer %= MOD

print(answer)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list( map(int, input().split() ) )
kai = 1
M = 10**9+7
result = 0
for i in range(1,N):
    kai *= i
    
for i in range(N-1):
    result += kai * (a[N-1] - a[i]) // ( i+1 )
    result = result%M

print( result )

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
X = list(map(int, input().split()))
Y = []
for i in range(N - 1):
    Y.append(X[i + 1] - X[i])

Z = [1]
f = 1
count = 0
N_F = math.factorial(N - 1)
for i in range(1, N):
    Z.append(Z[i - 1] * (i + 1) + math.factorial(i))
    count += Z[i - 1] * N_F // math.factorial(i) * Y[i - 1]

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = float('INF')
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
X = LI()
d = [0] * (n - 1)
for i in range(n - 1):
    d[i] = X[i + 1] - X[i]


fac = factorial(n - 1)


acc = list(accumulate([fac // i for i in range(1, n)]))
ret = 0
for j in range(n - 1):
    ret += acc[j] * d[j]


print(ret % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
pr=10**9+7
N=int(input())
x = tuple(map(int, input().split()))
t=2
b=[1]
for i in range(N-2):
    a=[None]*(t)
    for j in range(t-1):
        a[j]=b[j]*(t)%pr
    a[-1]=(a[-2]+b[0])%pr
    b=a
    t+=1
s=0
for i in range(N-1):
    s+=(x[i+1]-x[i])*b[i]%pr
print(s%pr)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
X = rl()
MOD = 10 ** 9 + 7
limit = math.factorial(N-1)
last = X[-1]
X = [last - x for x in X] #最後までの距離
answer = 0
for i in range(1, N):
    answer += X[i-1] * limit // i
    answer %= MOD

print(answer)

Submission status: Time Limit Exceeded

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

kai = [1]
tmp = 1
for i in range(1, n+1):
    tmp *= i
    tmp %= mod
    kai.append(tmp)

ans = 0
for i in range(1, n):
    tmp = 0
    for j in range(1, n-i+1):

        a = x[i+j-1] - x[i-1]
        a %= mod

        a *= kai[n-1]
        a %= mod

        if j != n-i:
            a *= kai[j-1]
            a %= mod

            a *= pow(kai[j+1], mod-2, mod)
            a %= mod

        else:
            a *= pow(j, mod-2, mod)
            a %= mod

        #print(i, j, a)

        ans += a
        ans %= mod


    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class PERM_COMB_MOD():
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

    def perm(self, n, k):
        if n < k : return 0
        if n < 0 or k < 0:return 0
        return self.fac[n] * self.finv[n-k] % self.mod % self.mod

    def comb(self, n, k):
        if n < k : return 0
        if n < 0 or k < 0:return 0
        return self.fac[n] * (self.finv[k] * self.finv[n-k] % self.mod) % self.mod

mod = 10**9+7
P = PERM_COMB_MOD(2*10**5, mod=mod)

n = int(input())
x = list(map(int, input().split()))
base = x[-1]-x[0]
left = []
k = n-1
for i in range(k):
    a = P.perm(k, k-(i+1))*P.fac[i]
    left.append(a)
ans = base*P.fac[k]
for i in range(k):
    for j in range(1, n-1-i):
        ans += left[j]*(x[i+j+1]-x[i+j])
        ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
X = np.array(rl())
MOD = 10 ** 9 + 7
limit = math.factorial(N-1)
last = X[-1]
X = [last - x for x in X[:-1]] #最後までの距離
Y = np.array([limit // i for i in range(1, N)])
Z = X * Y
answer = Z.sum()%MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
ls_x = list(map(int,input().split()))
c1 = math.factorial(n-1)
c = [c1]
cn = 0
ans = 0
for i in range(n-1):
    ans -= (ls_x[i] * c1//(i+1))
    cn += (c1//(i+1))
    ans = int(ans % (10**9+7))
    cn = int(cn % (10**9+7))

ans += cn * ls_x[n-1]
ans = int(ans % (10**9+7))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = [int(x) for x in input().split()]
inf = 10**9+7
a = 1
for i in range(n-1, 0, -1):
    a *= i
b = a
key = 0
ans = 0
for i in range(n-1):
    key += a//(i+1)
    key %= inf
    ans += key*(x[i+1]-x[i])
    ans %= inf
    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
X = rl()
MOD = 10 ** 9 + 7
limit = math.factorial(N-1)
last = X[-1]
X = [last - x for x in X] #最後までの距離
answer = 0
for i in range(1, N):
    answer += (X[i-1] * limit // i)%MOD
    answer %= MOD

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())

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

mod = 10**9 + 7

li = []
for i in range(n-1):
    li.append(x[i+1] - x[i])

dp = [0] * (n-1)
dp2 = [0] * (n-1)
dp3 = [0] * n
dp3[0] = 1

for i in range(n-1):
    dp3[i+1] = dp3[i] * (i+2)

dp[0] = x[1] - x[0]
dp2[0] = 1

for i in range(n-2):
    dp2[i+1] = dp2[i] * (i+2) + dp3[i]

ans = 0

for i in range(n-2):
    dp[i+1] = dp[i] * (i+2) + (x[i+2] - x[i+1]) * dp2[i+1]
    dp[i+1] %= mod

print(dp[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

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


MOD = 10 ** 9 + 7

def solve_fast(N, As):

    dists = []
    for i in range(N - 1):
        dists.append(As[i + 1] - As[i])
    # print("dists = ", dists)

    dist_sum = sum(dists)

    factorial = 1
    for n in range(N - 1): factorial *= (n + 1)

    ans = 0
    for n in range(2, N + 1):
        # print("fact {} * dist {} :".format(factorial, dist_sum))
        ans += factorial * dist_sum
        factorial *= (n - 1)
        factorial //= n
        dist_sum -= dists[n - 2]

    return ans % MOD

print(solve_fast(N, As))

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
ls_x = list(map(int,input().split()))
c1 = math.factorial(n-1)
c = [c1]
ans = 0
for i in range(2,n):
    # print(i)
    c.append(c[0]//i)
cn = sum(c)
for i in range(n-1):
    ans -= (ls_x[i] * c[i])
    ans = int(ans % (10**9+7))
ans += cn * ls_x[n-1]
ans = int(ans % (10**9+7))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
l = list(map(int, input().split()))
lr=[]
for i in range(n):
  a=l[-1]-l[i]
  lr.append(a)


maxim=sum(lr)
mini=lr[0]
ans=0
for i in range(mini,maxim+1):
  ans+=i/(n-1)
print(int(ans*math.factorial(n-1)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from itertools import permutations
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

MOD = 1000000000 + 7

N, *X = map(int, read().split())
X = np.array(X)

cnt = 1
for i in range(1, N):
    cnt *= i

cnt %= MOD
ans = 0

l = list(permutations(range(1, N)))
for per in l:
    ans += np.abs(np.diff(np.array(list(per) + [N]))).sum()

ans /= len(l) 
ans *= cnt

print(int(ans % MOD))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

# In[]:
N = inp()
xx = inpl()

# N = 3
# xx = 1,2,3

# In[]:
aa = [1]
fac = 1
for L in range(2,N):
    fac *= L-1
    naa = [fac]*L
    for i in range(L):
        if i < L-1:
            naa[i] += (L-i-1)*aa[i]
        if 1 <= i:
            naa[i] += (i+1)*aa[i-1]
        naa[i] %= mod

    aa = naa[:]
    # print(aa)

# print(aa)

# In[]:
dx = [xx[i]-xx[i-1] for i in range(1,N)]
# print(dx)

# In[]:
ans = 0
# print(aa)
# print(dx)
for a,d in zip(aa,dx):
    ans += a*d

print(ans%mod)

Submission status: Time Limit Exceeded

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

bl = []

for i in range(n-1):
    bl.append(xl[i+1] - xl[i])

import math
a = math.factorial(n-1)
c = a
ans = 0

for i in range(n-1):
    ans += c * bl[i]
    ans %= 10**9 + 7
    c += a // (i+2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=[[]for i in range(n)]
A[0].append(1)
for i in range(2,n+1):
  for j in range(i-1):
    A[i-1].append(A[i-2][j]*i)
  A[i-1].append(A[i-1][-1]+A[i-2][0])
X=list(map(int,input().split()))
Y=[X[1]-X[0]]
for i in range(2,n):
  Y.append(X[i]-X[i-1])
ans=0
for i in range(n-1):
  ans=(ans+A[n-2][i]*Y[i])%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
    
if N > 2000:
  print(0)
  
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

mod = 10**9+7 #出力の制限
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 )

import math

ans = 0
for i in range(1, N):
    ans += cmb(N-1, N-i, mod)*math.factorial(i-1)*math.factorial(N-i-1)*(A[N-1]-A[i-1])
    ans %= mod
    for j in range(i+1, N):
        ans += cmb(N-1, j-i+1, mod)*math.factorial(N-j+i-2)*math.factorial(j-i-1)*(A[j-1]-A[i-1])
        ans %= mod
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
n = int(input())
F = [1]*(n+1)
for i in range(n):
  F[i+1] = F[i]*(i+1) % MOD
X = list(map(int, input().split()))
D = [X[i+1]-X[i] for i in range(n-1)]
T = [1]*n
for i in range(2, n):
  T[i] = T[i-1]*i+F[i-1]
  T[i] %= MOD
t = 1
for i in range(1, n-1):
  t *= (n-i) % MOD
  T[n-1-i] *= t % MOD
ans = 0
for i in range(1, n):
  ans += D[i-1]*T[i]
  ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# modulo:mod

# inverse x^(-1)
def inv(x):
    global mod
    return pow(x,mod-2,mod)

# factorial x!
def fact(x):
    global mod
    res=1
    for i in range(2,x+1):
        res=res*i%mod
    return res

# combination nCr
def combi(n,r):
    if r<0 or r>n:
        return 0
    else:
        return fact(n)*inv(fact(r))*inv(fact(n-r))%mod

mod=10**9+7

N=int(input())
x=[0]
x.extend(list(map(int,input().split())))
invs=[inv(d) for d in range(N)]
# print(invs)
ans=0
for i in range(1,N):
    for j in range(i+1,N):
        temp=(x[j]-x[i])*invs[j-i]*invs[j-i+1]%mod
        ans=(ans+temp)%mod
    temp=(x[N]-x[i])*invs[N-i]%mod
    ans=(ans+temp)%mod
ans=ans*fact(N-1)%mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# modulo:mod

# inverse x^(-1)
def inv(x):
    global mod
    return pow(x,mod-2,mod)

# factorial x!
def fact(x):
    global mod
    res=1
    for i in range(2,x+1):
        res=res*i%mod
    return res

# combination nCr
def combi(n,r):
    if r<0 or r>n:
        return 0
    else:
        return fact(n)*inv(fact(r))*inv(fact(n-r))%mod

mod=10**9+7

N=int(input())
x=[0]
x.extend(list(map(int,input().split())))

ans=0
for i in range(1,N):
    for j in range(i+1,N):
        temp=(x[j]-x[i])*inv((j-i)*(j-i+1))%mod
        ans=(ans+temp)%mod
    temp=(x[N]-x[i])*inv(N-i)%mod
    ans=(ans+temp)%mod
ans=ans*fact(N-1)%mod

print(ans)

Submission status: Accepted

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

mod = 10**9+7
inv = [0,1]
for i in range(2,N):
  inv.append(inv[mod % i]*(mod - mod//i) % mod)

fac = 1
for i in range(1,N):
    fac *= i
    fac %= mod

ans = 0
cur = 0
for i in range(1,N):
    cur += fac*inv[i]
    cur %= mod
    ans += cur*(x[i]-x[i-1])
    ans %= mod
print(ans)

Submission status: Accepted

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

# コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
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
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
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)

ans=0
nn=[g1[n-1]]
tmp=g1[n-1]
for i in range(2,n):
  tmp+=g1[n-1]*pow(i,mod-2,mod)
  tmp%=mod
  nn.append(tmp)
  
for i in range(n-1):
  d=x[i+1]-x[i]
  ans+=d*nn[i]
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:


def factorials_with_inv(k,mod):
    """
    0! ... k! とそれらのmod逆元を求めて返す
    """
    fac = [1]*(k+1)
    inv = [1]*(k+1)
    t = 1
    for i in range(1,k+1):
        t *= i
        t %= mod
        fac[i] = t

    t = pow(t,-1,mod)
    for i in reversed(range(1,k+1)):
        inv[i] = t
        t *= i
        t %= mod

    return fac, inv

def solve(X):
    MOD = 10**9+7
    N = len(X)-1
    DX = [b-a for a,b in zip(X,X[1:])]

    fac,inv = factorials_with_inv(N,MOD)
    res = 0
    s2 = 0
    s1 = 0
    s0 = 1

    P = fac[N]
    for k,d in enumerate(DX, start=2):
        x = s0-s1*(k-1)
        s2 = s1
        s1 = s0
        s0 = s0*k + x*(k+1) - s2
        x %= MOD
        s2 %= MOD
        s1 %= MOD
        s0 %= MOD
        res += x*P*inv[k-1]*d
        res %= MOD
    return res

if __name__ == '__main__':
    N = int(input())
    X = list(map(int,input().split()))
    print(solve(X))

Submission status: Accepted

Solution code:
N = int(input())
X = list(map(int, input().split()))
MOD = 10**9+7
S = 0
res = 0
F = 1
for i in range(1,N):
    S += pow(i,MOD-2,MOD)
    res += (X[i]-X[i-1])*S
    res%=MOD
    F*=i
    F%=MOD
print(res*F%MOD)

Submission status: Accepted

Solution code:
def ext_euc(a, b):
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euc(a, mod)
    return x % mod


def mod_fac(a, mod):
    ret = 1
    for aa in range(1, a + 1):
        ret *= aa
        ret %= mod
    return ret


def main():
    MOD = 10**9 + 7
    N = int(input())
    X = list(map(int, input().split()))
    ans = 0
    for n in range(N - 1):
        ans += (X[N - 1] - X[n]) * mod_inv(n + 1, MOD)
    ans *= mod_fac(N - 1, MOD)
    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N = I()
X = LI()
mod = 10**9+7
Y = [X[i+1]-X[i] for i in range(N-1)]

r = 1  # (N-1)!
for i in range(1,N):
    r *= i
    r %= mod

C = [r]  # Ci = (N-1)!*(1/1+1/2+…+1/i)
for i in range(2,N):
    C.append((C[-1]+r*pow(i,mod-2,mod)) % mod)

ans = 0
for y,c in zip(Y,C):
    ans += y*c
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
n, *x = map(int, open(0).read().split())
mod = 10 ** 9 + 7
fac = [1] * n
for i in range(1, n):
    fac[i] = fac[i - 1] * i % mod

ans = 0
p = 0

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

print(ans * fac[n - 1] % mod)

Submission status: Accepted

Solution code:
n, *x = map(int, open(0).read().split())

mod = 10 ** 9 + 7

y = []
for i in range(n - 1):
    y.append(x[i + 1] - x[i])

fac = [1] * (n + 1)
for i in range(1, n):
    fac[i] = fac[i - 1] * i % mod

dp = [0] * n
ans = 0
p = 0

for i in range(n - 1):
    p = (p + pow(i + 1, mod - 2, mod))
    ans = (ans + p * y[i]) % mod

print(ans * fac[n - 1] % mod)