The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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

Ieșire

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>