1777B - Emordnilap - 900

1777B - Emordnilap (combinatorics, greedy, math, 900)

Statement

In this problem, we need to find the “beauty” of all permutations of a certain length n. The beauty of a permutation is defined as the number of inversions in an array that is created by combining the permutation and its reverse.

Logic

The key insight is that every permutation of length n has the same beauty.

This is because the structure of the array created by concatenating a permutation with its reverse ensures that there will always be the same number of inversions, regardless of the order of the numbers in the original permutation.

Therefore, we can calculate the beauty of a single permutation and then multiply by the number of possible permutations (which is n!) to get the total sum of the beauties.

Solution

def solve():
    n = int(input())
    MOD = 10**9 + 7

    # Calculate the total number of inversion pairs in the array
    inversion_pairs = n * (n - 1)

    # Find the factorial of n
    fact = 1
    for i in range(1, n+1):
        fact = fact * i % MOD  # requirement: size n modulo 1000000007(109+7)

    # The sum of the beauty of all permutations can be found by multiplying
    # the number of inversion pairs by the factorial of n
    res = (fact * inversion_pairs) % MOD
    print(res)


for _ in range(int(input())):
    solve()