Good Trip (Codeforces 1925D)
Tags: Math, probabilities

There are $$$n$$$ children in a class, $$$m$$$ pairs among them are friends. The $$$i$$$-th pair who are friends have a friendship value of $$$f_i$$$. The teacher has to go for $$$k$$$ excursions, and for each of the excursions she chooses a pair of children randomly, equiprobably and independently. If a pair of children who are friends is chosen, their friendship value increases by $$$1$$$ for all subsequent excursions (the teacher can choose a pair of children more than once). The friendship value of a pair who are not friends is considered $$$0$$$, and it does not change for subsequent excursions. Find the expected value of the sum of friendship values of all $$$k$$$ pairs chosen for the excursions (at the time of being chosen). It can be shown that this answer can always be expressed as a fraction $$$\dfrac{p}{q}$$$ where $$$p$$$ and $$$q$$$ are coprime integers. Calculate $$$p\cdot q^{-1} \bmod (10^9+7)$$$.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$). Description of the test cases follows.The first line of each test case contains $$$3$$$ integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le m \le \min \Big(10^5$$$, $$$ \frac{n(n-1)}{2} \Big)$$$, $$$1 \le k \le 2 \cdot 10^5$$$) — the number of children, pairs of friends and excursions respectively.The next $$$m$$$ lines contain three integers each — $$$a_i$$$, $$$b_i$$$, $$$f_i$$$ — the indices of the pair of children who are friends and their friendship value. ($$$a_i \neq b_i$$$, $$$1 \le a_i,b_i \le n$$$, $$$1 \le f_i \le 10^9$$$). It is guaranteed that all pairs of friends are distinct.It is guaranteed that the sum of $$$n$$$ and sum $$$m$$$ over all test cases does not exceed $$$10^5$$$ and the sum of $$$k$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print one integer — the answer to the problem.

Note: For the first test case, there are no pairs of friends, so the friendship value of all pairs is $$$0$$$ and stays $$$0$$$ for subsequent rounds, hence the friendship value for all excursions is $$$0$$$.For the second test case, there is only one pair possible $$$(1, 2)$$$ and its friendship value is initially $$$1$$$, so each turn they are picked and their friendship value increases by $$$1$$$. Therefore, the total sum is $$$1+2+3+\ldots+10 = 55$$$.For the third test case, the final answer is $$$\frac{7}{9} = 777\,777\,784\bmod (10^9+7)$$$.

Sample Inputs:
4
100 0 24
2 1 10
1 2 1
3 1 2
2 1 1
5 2 4
1 2 25
3 2 24

Sample Outputs:
0
55
777777784
40000020

Solution (Python):
import sys
input = lambda : sys.stdin.buffer.readline().decode().strip()
print = lambda *args, **kwargs: sys.stdout.write(' '.join(map(str, args)) + '\n', **kwargs)

def InputList(Dtype=int):
    return list(map(Dtype, input().split()))
from random import randint
RND = randint(1, 10 ** 9)
inf = float('inf')
M = 10 ** 9 + 7

def Nc2(n):
    return n * (n - 1) // 2 % M

def solve():
    (n, m, k) = InputList()
    fSum = 0
    for _ in range(m):
        (_, _, f) = InputList()
        fSum += f
    t = Nc2(n)
    tInv = pow(t, M - 2, M)
    fSum %= M
    res = 0
    for i in range(k):
        res += (fSum + i * m * tInv) * tInv
        res %= M
    return res
for i in range((t := int(input()))):
    ans = solve()
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(5 * 10 ** 4)

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, m, k) = readInts()
    S = 0
    for _ in range(m):
        (a, b, f) = readInts()
        S += f
    p = 2 % mod * pow(n * (n - 1), mod - 2, mod) % mod
    ans = S * p % mod
    S = (S + m * p) % mod
    for _ in range(k - 1):
        ans += S * p % mod
        ans %= mod
        S = (S + m * p) % mod
    return ans
mod = pow(10, 9) + 7
for _ in range(int(input())):
    print(solve())

Solution (Python):
MOD = int(1000000000.0 + 7)

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def gcd_extended(a, b):
    if b == 0:
        return (a, 1, 0)
    (d, x, y) = gcd_extended(b, a % b)
    return (d, y, x - a // b * y)

def mod_inverse(n):
    (_, x, _) = gcd_extended(n, MOD)
    return (x + MOD) % MOD

def calculate_mod(p, q):
    g = gcd(p, q)
    p //= g
    q //= g
    q_inv = mod_inverse(q)
    result = p * q_inv % MOD
    return result
input_str = input()
inputs = input_str.split()
t = int(inputs[0])
for i in range(t):
    input_str = input()
    inputs = input_str.split()
    n = int(inputs[0])
    m = int(inputs[1])
    k = int(inputs[2])
    s = 0
    for j in range(m):
        input_str = input()
        inputs = input_str.split()
        a = int(inputs[0])
        b = int(inputs[1])
        f = int(inputs[2])
        s += f
    p = 2 * s * k * n * (n - 1) + 2 * m * k * (k - 1)
    q = n * n * (n - 1) * (n - 1)
    print(calculate_mod(p, q))