2181 - inversum

Cerința

Fie o permutare P a mulțimii {1, 2, 3, ... N}. Se numește inversiune o pereche (i, j), i < j pentru care P[i] > P[j]. Fie funcția M(N) = suma numărului de inversiuni a fiecărei permutare a numerelor {1, 2, 3, ... N}. Pentru N dat, să se calculeze M(N) modulo 1000003.

Date de intrare

Programul citește de la tastatură numărul N.

Date de ieșire

Programul va afișa pe ecran numărul S, reprezentând valoarea M(N) modulo 1000003.

Restricții și precizări

• 1 ≤ N ≤ 1.000.000

Exemplu:

Intrare

3

Ieșire

9

Rezolvare

<syntaxhighlight lang="python3"> MOD = 1000003

def calculate_inversion_sum(n):

   total_inversions = 0
   factorial = 1

   for i in range(1, n + 1):
       factorial *= i

       current_inversions = i * (n - i)

       total_inversions += current_inversions

       total_inversions %= MOD

   return total_inversions

def main():

   n = int(input())

   inversion_sum = calculate_inversion_sum(n)
   print(inversion_sum)

if __name__ == "__main__":

   main()

</syntaxhighlight>