Problem:


Score : 500 points

Problem Statement

For two sequences S and T of length N consisting of 0 and 1, let us define f(S, T) as follows:

Consider repeating the following operation on S so that S will be equal to T. f(S, T) is the minimum possible total cost of those operations.

Change S_i (from 0 to 1 or vice versa). The cost of this operation is D \times C_i, where D is the number of integers j such that S_j \neq T_j (1 \leq j \leq N) just before this change.

There are 2^N \times (2^N - 1) pairs (S, T) of different sequences of length N consisting of 0 and 1. Compute the sum of f(S, T) over all of those pairs, modulo (10^9+7).

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq C_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
C_1 C_2 \cdots C_N

Output

Print the sum of f(S, T), modulo (10^9+7).

Sample Input 1

1
1000000000

Sample Output 1

999999993

There are two pairs (S, T) of different sequences of length 2 consisting of 0 and 1, as follows:

S = (0), T = (1): by changing S_1 to 1, we can have S = T at the cost of 1000000000, so f(S, T) = 1000000000.

S = (1), T = (0): by changing S_1 to 0, we can have S = T at the cost of 1000000000, so f(S, T) = 1000000000.

The sum of these is 2000000000, and we should print it modulo (10^9+7), that is, 999999993.

Sample Input 2

2
5 8

Sample Output 2

124

There are 12 pairs (S, T) of different sequences of length 3 consisting of 0 and 1, which include:

S = (0, 1), T = (1, 0)

In this case, if we first change S_1 to 1 then change S_2 to 0, the total cost is 5 \times 2 + 8 = 18. We cannot have S = T at a smaller cost, so f(S, T) = 18.

Sample Input 3

5
52 67 72 25 79

Sample Output 3

269312



Sample input:
1
1000000000


Sample output:
999999993

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
C = list(sorted(map(int, input().split()), reverse=True))

MAX = 2 * 10 ** 5 + 5
MOD = 10 ** 9 + 7

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod


def com(n, r, mod):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def p(n, r, mod):
    return fac[n] * finv[n - r] % mod
    
comInit(MOD)

def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

ans = 0
base = my_pow(2, N, MOD) % MOD
for i, c in enumerate(C):
    now = my_pow(2, N - i - 1, MOD)
    tot = 0
    for d in range(i + 1):
        tot += (d + 1) * c * com(i, d, MOD) 
        tot %= MOD
    ans += (tot * now) % MOD
    ans %= MOD
print(ans * base % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
C = list(sorted(map(int, input().split()), reverse=True))

MAX = 2 * 10 ** 5 + 5
MOD = 10 ** 9 + 7

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod


def com(n, r, mod):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def p(n, r, mod):
    return fac[n] * finv[n - r] % mod
    
comInit(MOD)

def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

ans = 0
base = my_pow(2, N, MOD) % MOD
for i, c in enumerate(C):
    now = my_pow(2, N - i - 1, MOD)
    tot = 0
    for d in range(i + 1):
        tot += (d + 1) * c * com(i, d, MOD) 
        tot %= MOD
    ans += (tot * now * base) % MOD
    ans %= MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
C = list(sorted(map(int, input().split()), reverse=True))

MAX = 2 * 10 ** 5 + 5
MOD = 10 ** 9 + 7

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod


def com(n, r, mod):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def p(n, r, mod):
    return fac[n] * finv[n - r] % mod
    
comInit(MOD)

def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

ans = 0
base = my_pow(2, N, MOD)
for i, c in enumerate(C):
    now = my_pow(2, N - i - 1, MOD)
    tot = 0
    for d in range(i + 1):
        tot += (d + 1) * c * com(i, d, MOD) 
    ans += tot * now * base % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
# 各々の要素が何番目に何回数えられるかを考える。
import sys

input = sys.stdin.buffer.readline

n = int(input())
C = list(map(int, input().split()))
C.sort(reverse=True)
mod = 10 ** 9 + 7
N = n + 5
bikkuri = [0] * N
bikkuri[0] = 1
gyaku = [0] * N
for i in range(1, N):
    bikkuri[i] = (i * bikkuri[i - 1]) % mod
gyaku[N - 1] = pow(bikkuri[N - 1], mod - 2, mod)
for i in range(N - 1, 0, -1):
    gyaku[i - 1] = (gyaku[i] * i) % mod


def comb(n, r):
    if r < 0 or n - r < 0:
        return 0
    return (bikkuri[n] * gyaku[r] * gyaku[n - r]) % mod


ans = 0
for i in range(n):
    for a in range(i + 1):
        ans += comb(i, a) * (a + 1) * C[i] * pow(2, n - (i + 1), mod)
        ans %= mod
ans *= pow(2, n, mod)
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 各々の要素が何番目に何回数えられるかを考える。
import sys

input = sys.stdin.buffer.readline

n = int(input())
C = list(map(int, input().split()))
C.sort(reverse=True)
mod = 10 ** 9 + 7
N = n + 5
bikkuri = [0] * N
bikkuri[0] = 1
gyaku = [0] * N
for i in range(1, N):
    bikkuri[i] = (i * bikkuri[i - 1]) % mod
gyaku[N - 1] = pow(bikkuri[N - 1], mod - 2, mod)
for i in range(N - 1, 0, -1):
    gyaku[i - 1] = (gyaku[i] * i) % mod


def comb(n, r):
    if r < 0 or n - r < 0:
        return 0
    return (bikkuri[n] * gyaku[r] * gyaku[n - r]) % mod


ans = 0
for i in range(n):
    for k in range(n + 1):
        for a in range(i + 1):
            ans += comb(i, a) * (a + 1) * C[i] * comb(n - (i + 1), k - (a + 1))
            ans %= mod
ans *= pow(2, n, mod)
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def resolve():
    MOD = 10 ** 9 + 7
    N = int(input())
    C = sorted(map(int, input().split()))
    P = [1] * (N + 1)
    for i in range(N):
        P[i + 1] *= P[i] * 2
    ans = 0
    for i in range(N):
        # 各ビットの係数: (2^r + 2^r-1 * r) * 2^l
        l, r = i, N - i - 1
        now = P[r]
        if r != 0:
            now += P[r - 1] * r % MOD
        now *= P[l]
        now *= C[i]
        ans += now % MOD
        ans %= MOD
    ans *= P[N]
    print(ans % MOD)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import itertools
N=int(input())
C=list(set(map(int,input().split())))
C_sorted=sorted(C)
def LC(X):
  k=0
  for j in range(len(X)):
    k+=(len(X)-j)*X[j]
  return k

def f(D):
  Comb=[]
  for pair in itertools.combinations(C_sorted,D):
    Comb.append(pair)
  Sum_D=0
  for i in range(len(Comb)):
    Sum_D+=LC(Comb[i])
  return Sum_D

t=0
for D in range(1,N+1):
  t+=f(D)
print(((2**N)*t)%((10**9)+7))

Submission status: Time Limit Exceeded

Solution code:
number=10**9+7

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

c.sort(reverse=True)
sum=0
for i in range(1, n+1):
    sum=(sum+(4**(n-1))*(i+1)*c[i-1])%number
print(sum)

Submission status: Time Limit Exceeded

Solution code:
number=10**9+7

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

c=sorted(c, reverse=True)
sum=0
for i in range(1, n+1):
    sum=(sum+(4**(n-1))*(i+1)*c[i-1])%number
print(sum)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    mod = 10**9 + 7

    n = int(input())
    c = list(map(int, input().split()))
    c.sort()
    res = 0
    b = int(pow(2, n, mod))
    for i in range(n):
        l = int(pow(2, i, mod))
        r = int(pow(2, n-i-1, mod) + (n-i-1)*pow(2, n-i-2))
        res += b*c[i]*l*r % mod
    print(res%mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
c = list(map(int,input().split()))
mod = 10**9+7
c.sort()
ans = 0
for i in range(n):
    ans += c[i]*(2+n-1-i)*4**(n-1)
    ans %= mod

ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    N = int(input())
    mod = 10**9 + 7
    C = list(map(int, input().split()))
    C.sort()
    c = cmbs(mod)
    r = 0
    for i, v in enumerate(C):
        t = 0
        for j in range(i, N):
            t += (j - i + 1) * c.cmb(N-i-1, j-i)
        t *= v * pow(2, i, mod)
        r += t
    r *= pow(2, N, mod)
    r %= mod
    return r
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
# Tを固定して、後で2**N倍する
N = ir()
C = lr()
C.sort(reverse=True)
diff = 0
answer = 0
base = 2 ** N
for i in range(N):
    answer += (diff//2 + base//2) * C[i]
    diff += base // 2
    answer %= MOD

for i in range(N):
    answer *= 2
    answer %= MOD

print(answer%MOD)
# 51

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    c = LI()
    c.sort()
    if n == 1:
        print(2*c[0]%mod)
        return
    k = 1<<(n-2)
    f = [k*(i+2)*pow(2,n,mod)%mod for i in range(n)][::-1]
    ans = 0
    for i in range(n):
        ans += c[i]*f[i]
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    c = LI()
    c.sort()
    if n == 1:
        print(2*c[0]%mod)
        return
    k = 1<<(n-2)
    f = [k*(i+2)*(1<<n)%mod for i in range(n)][::-1]
    ans = 0
    for i in range(n):
        ans += c[i]*f[i]
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,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
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
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()
    C=sorted(LI())
    ans = ModInt(0)
    for i,c in enumerate(C):
        R = ModInt(N-i-1)
        ans += (2**i) * c * ( 2**R + R*(2**(R-1)) )
    ans *= 2**N
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Ciの値でsortする、Tを0000で固定した後、最後に2**N倍
N = ir()
C = np.array(lr())
MOD = 10 ** 9 + 7
C.sort()
two_power = np.array([(1+N-i) * 2**(N-2) % MOD if i < N-1 else 2 ** i % MOD for i in range(N)])
answer = (C * two_power % MOD).sum() * 2**N
print(answer%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Ciの値でsortする、Tを0000で固定した後、最後に2**N倍
N = ir()
C = np.array(lr())
MOD = 10 ** 9 + 7
C.sort()
two_power = np.array([(1+N-i) * 2**(N-2) if i < N-1 else 2 ** i for i in range(N)])
answer = (C * two_power % MOD).sum() * 2**N
print(answer%MOD)

Submission status: Time Limit Exceeded

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

#最初に全ての必要なcnvを計算する
#今回はN<=n-1,R<=-(-(n-1)//2)
#注）n, r = 0 も含める
cnvs = [[1] * (-(-(n-1) // 2) + 1) for _ in range(n)]
for N in range(n):
    for R in range(1 , -(-N // 2) + 1):
        cnvs[N][R] = cnvs[N][R-1] * (N - R + 1) // R

def cnv(n,r):
    if n < r:
        return 0
    
    if r > n-r:
        return cnv(n, n-r)

    return  cnvs[n][r] % (10**9 + 7)

cs.sort()
ans = 0
#a = 違う数字の個数
for a in range(1,n+1):
    # c = コスト
    for i, c in enumerate(cs):
        c_index = i + 1
        for d in range(1,a+1):
            # d = 左から何番目の「違う数字」か
            # a + 1 - d = かかるコストのおもみ 
            ans += ((a + 1 - d) * c * cnv(c_index - 1, d - 1) * cnv(n - c_index, a - d)) % (10**9 + 7)

ans *= 2**n

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

Submission status: Time Limit Exceeded

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

#最初に全ての必要なcnvを計算する
#今回はN<=n-1,R<=-(-(n-1)//2)
#注）n, r = 0 も含める
cnvs = [[1] * (-(-(n-1) // 2) + 1) for _ in range(n)]
for N in range(n):
    for R in range(1 , -(-N // 2) + 1):
        cnvs[N][R] = cnvs[N][R-1] * (N - R + 1) // R

def cnv(n,r):
    if n < r:
        return 0
    
    if r > n-r:
        return cnv(n, n-r)

    return  cnvs[n][r]

cs.sort()
ans = 0
#a = 違う数字の個数
for a in range(1,n+1):
    # c = コスト
    for i, c in enumerate(cs):
        c_index = i + 1
        for d in range(1,a+1):
            # d = 左から何番目の「違う数字」か
            # a + 1 - d = かかるコストのおもみ 
            ans += (a + 1 - d) * c * cnv(c_index - 1, d - 1) * cnv(n - c_index, a - d)

ans *= 2**n

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

Submission status: Time Limit Exceeded

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

def cnv(n,r):
    if n < r:
        return 0

    res = 1
    for i in range(1, r+1):
        res = res * (n - (i - 1)) // i
    return  res

cs.sort()
ans = 0
#a = 違う数字の個数
for a in range(1,n+1):
    # c = コスト
    for i, c in enumerate(cs):
        c_index = i + 1
        for d in range(1,a+1):
            # d = 左から何番目の「違う数字」か
            # a + 1 - d = かかるコストのおもみ 
            ans += (a + 1 - d) * c * cnv(c_index - 1, d - 1) * cnv(n - c_index, a - d)

ans *= 2**n

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

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7

n=int(input())
c=list(map(int, input().split()))
c.sort(reverse=True)
ans=0
x=2**(2*n-1)
d=x//2
for i in range(n):
    ans+=(x+i*d)*c[i]
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7

n=int(input())
c=list(map(int, input().split()))
c.sort(reverse=True)
ans=0
x=2**(2*n-1)
d=x//2
for i in range(n):
    ans=(ans+(x+i*d)*c[i])%MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

N = int(input())
*C, = map(int, input().split())
C.sort()
mod = 10**9+7

ans = 0
for k in range(1, N+1):
    for m in combinations(C, k):
        for j, p in enumerate(m):
            ans += (k-j)*p

ans *= pow(2, N, mod)
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
mod = 10 ** 9 + 7
ans = 1
for _ in range(n):
  ans *= 2
cef = [ans//2]
for i in range(n-1):
  tmp = cef[-1] + ans // 4
  tmp %= mod
  cef.append(tmp)
son = 0
for i in range(n):
  son += cef[i] * a[i]
  son %= mod
ans *= son
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

# ゼロ埋め
# list = [0] * N

# 二次元配列
# [[inf, inf, inf], [inf, inf, inf]]
# dp = [[float('inf')] * (H + 1) for i in range(N + 1)]

def solve(N, A):
    A.sort()
    two = [0] * (N + 1)
    for i in range(N + 1):
        two[i] = 2 ** i

    ans = 0
    for i in range(N):
        l = i
        r = N-i-1
        now = two[r]
        if r != 0:
            now += two[r-1] * r
        now *= two[l]
        now *= A[i]
        ans += now
    
    ans *= two[N]

    return ans % MOD

    return 0

# S = input()
N = int(input())
# H, N = map(int, input().split())
A = list(map(int, input().split()))
# B = [int(input()) for _ in range(n)]
# A = []
# B = []
# for _ in range(N):
#     a, b = list(map(int, input().split()))
#     A.append(a)
#     B.append(b)

print(solve(N, A))

Submission status: Time Limit Exceeded

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

MM = 10 ** 9 + 7
j = 2 ** n %MM

s = 0
cost = 0
while True:
    if s >= 1 << n:
        break
    kumi = format(s,'0'+ str(n)+ 'b')
    ct = [v for i,v in enumerate(c) if kumi[i] == '1']
    ct.sort()
    cos = sum([len(ct[i:]) * v for i, v in enumerate(ct)])
    cos = cos * (2 ** len(ct)) % MM  * (2 ** (n -len(ct))) %MM
    cost += cos
    s += 1
print(cost % MM)

Submission status: Time Limit Exceeded

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

N=input()
C=map(int, sys.stdin.readline().split())
C.sort()

mod=10**9+7
D=[]
d0=pow(2,N-1,mod)

#D：係数の配列の作成
for i in range(N):
    if i==0:
        D.append(d0)
    else:
        D.append( (2*D[-1]-d0)*pow(2,mod-2,mod)+d0 )

#Ci*Diを最小にするため、最小のCiに最大のDiを掛けるため、降順ソートする
D.sort(reverse=True)

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

ans=ans*pow(2,N,mod)

print ans%mod

Submission status: Time Limit Exceeded

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

N=input()
C=map(int, sys.stdin.readline().split())
C.sort()

mod=10**9+7
D=[]
d0=2**(N-1)

#D：係数の配列の作成
for i in range(N):
    if i==0:
        D.append(d0)
    else:
        D.append( (2*D[-1]-d0)/2+d0 )

#Ci*Diを最小にするため、最小のCiに最大のDiを掛けるため、降順ソートする
D.sort(reverse=True)

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

ans=ans*pow(2,N,mod)

print ans%mod

Submission status: Time Limit Exceeded

Solution code:
#import sys
#sys.setrecursionlimit(10**5)
MOD = 10**9+7

# input
N = int(input())
C = list(map(int, input().split()))
    
# process
C.sort(reverse=True)
ans = 0

if N == 1:
    ans = C[0]
else:
    for i in range(N):
        ans += C[i]*(2+i)*2**(N-2)
        
# output
print(ans*2**N%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)

MOD = 10**9+7

# input
N = int(input())
C = list(map(int, input().split()))
    
# process
C.sort()
ans = 0

# d:数列S、Tの異なる整数の数、idx:加算するコストの開始インデックス
def f(d, idx):
    if d == 0 or d + idx > N:
        return 1, 0

    t = 0
    cnt = 0
    for i in range(idx, N-d+1):
        c, r = f(d-1, i+1)
        t += d*C[i]*c + r
        cnt += c

    
    return cnt, t

ans = 0
for i in range(1, N+1):
    c, r = f(i, 0)
    ans += r
#    print("ans,r: {},{}".format(ans,r))

# output
print(ans*2**N%MOD)

Submission status: Time Limit Exceeded

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

mod=10**9+7
N = int(input())
C = [0]
C.extend(sorted(list(map(int,input().split())), reverse=True)) # 1-indexed, 降順

# print(C)
# C[i]が最後からj番目に操作される（コストが C[i]*j 掛かる）のは，c[1]~C[i-1]にj-1個操作すべきもの，すなわち，C[i]以上のものがあるとき。
# C[i+1]~C[N]の選び方は自由。
# ⇒ combi(i-1, j-1)*2**(N-i) を掛ける。

fact = [1]; invfact = [1]; pow2 = [1]
for k in range(1, N+1):
    fact.append(fact[-1] * k % mod)
    invfact.append(inv(fact[-1]))
    pow2.append(pow2[-1] * 2 % mod)

# print(fact)
# print(invfact)
# print(pow2)

ans=0
for i in range(1, N+1):
    for j in range(1, i+1):
        c = fact[i - 1] * invfact[j - 1] * invfact[i - j] * pow2[N - i] % mod
        # print(i, j, c)
        ans += C[i] * j * c
    ans = ans % mod

ans = ans * pow(2, N, mod) % mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
C = III()
C.sort()

ans = 0
for i in range(N):
    ans += 4**(N-1)*C[i]*(N-i+1)
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#E
n=int(input())
C=sorted(list(map(int,input().split())))
mod=10**9+7
sum=0
for i in range(n):
    l=i #その桁より左側の桁数(関係ないやつ)
    r=n-i #その桁より右側の個数(その桁自身も含む、1の個数を数えるやつ)
    if r==1:
        ans=2**l%mod
        ans=ans*C[i]%mod
        sum=(sum+ans)%mod
    else:
        ans=2**(r-1)%mod
        ans=(ans+(2**(r-2)%mod)*(r-1)%mod)%mod
        ans=ans*2**l%mod
        ans=ans*C[i]%mod
        sum=(sum+ans)%mod
print((sum*(2**n%mod)%mod))

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

C.sort()
C = C[::-1]

a0 = 2 ** (N - 1)
d = 2 ** (N - 2)
answer = 0
for i in range(N):
  answer = (answer + (a0 + d * i) * C[i]) % MOD
answer = (answer * pow(2, N, MOD)) % MOD
print(int(answer))

Submission status: Time Limit Exceeded

Solution code:
import itertools

num = int(input())
l = list(map(int, input().split()))

total = 0
for i in range(1, num+1):
    for diff_num in itertools.combinations(l, i):
        diff_num = sorted(list(diff_num))
        for j in range(len(diff_num)):
            total += diff_num[j] * (len(diff_num) - j)

total *= 2 ** num
ans = total % (10 ** 9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
list_c = list(map(int, input().split(" ")))
list_c.sort()


d = 10**9+7
cost = 1
res = 0

for i, c in enumerate(list_c) :
  #cost = (2 ** (N+i)) * c * (2**(N-i-2) * (N-i-1) + (2**(N-i-1)))
  cost = 1
  temp_n = N
  if(temp_n < 34) :
    cost *= int((2 ** (temp_n+temp_n-2) * (N-i+1)) * c) % d
    cost = cost % d
  else :
    temp_s = int(N / 32) - 1
    cost *= ((int(2 ** (32+32)) % d) ** temp_s) % d
    cost *= int((2 ** ((N%32+32)*2-2) * (N-i+1)) * c) % d
  
  #cost = (2 ** (N + N - 2) * (N-i+1)) * c
  res += cost
  res = res % d

print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
list_c = list(map(int, input().split(" ")))
list_c.sort()

d = 10**9+7
cost = 1
res = 0

for i, c in enumerate(list_c) :
  #cost = (2 ** (N+i)) * c * (2**(N-i-2) * (N-i-1) + (2**(N-i-1)))
  cost = 1
  temp_n = N
  while(True) :
    if(temp_n < 34) :
      cost *= int((2 ** (temp_n+temp_n-2) * (N-i+1)) * c) % d
      cost = cost % d
      break
    else :
      cost *= int(2 ** (32+32)) % d
      cost = cost % d
      temp_n -= 32
  
  #cost = (2 ** (N + N - 2) * (N-i+1)) * c
  res += cost
  res = res % d

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)


N = int(input())
C = list(map(int, input().split()))
C.sort()
MOD = 10**9 + 7


ans = 0
# どうも公式ドキュメントによると、組み込み関数のpowの第三引数に値渡すとMODとってくれるらしいので、完全に無駄
def pow_mod(x, n, mod):
    if n == 0:
        return 1 % mod
    elif n % 2 == 0:
        y = pow_mod(x, n//2, mod)
        return y * y % MOD
    else:
        return x * pow_mod(x, n-1, mod) % mod

for i in range(N):
    # 詳細は開設動画の通りだが、i桁目の右にr個の数字、左にlこの数字がある
    l = i
    r = N - i - 1
    # i桁目の寄与が C[i] * 2**l * (2**r + r * 2**(r-1))で、最後に2**Nをかける（Tのとり方が2**Nこあるので）
    # -> C[i] * 2**l * (2**(N+r) + r * 2**(r+N-1))
    ans += ((C[i] * pow_mod(2, l, MOD)) % MOD * (pow_mod(2, N+r, MOD) + r * pow_mod(2, N+r-1, MOD))) % MOD
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)
cnt = 0
a, b = 2**(n-1), 0 if n <= 1 else 2**(n-2)
for i, x in enumerate(c):
    cnt += (a + b*i) * x
    cnt %= MOD

print(cnt * (2 ** n % MOD) % MOD)