2181 - inversum
De la Universitas MediaWiki
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
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()