2181 - inversum: Diferență între versiuni
De la Universitas MediaWiki
(Pagină nouă: = Cerința = Fie o permutare <code>P</code> a mulțimii <code>{1, 2, 3, ... N}</code>. Se numește inversiune o pereche <code>(i, j), i < j</code> pentru care <code>P[i] > P[j]</code>. Fie funcția <code>M(N) = suma numărului de inversiuni a fiecărei permutare a numerelor {1, 2, 3, ... N}</code>. Pentru <code>N</code> dat, să se calculeze <code>M(N)</code> modulo <code>1000003</code>. = Date de intrare = Programul citește de la tastatură numărul <code>N</code>. = Dat...) |
(Nicio diferență)
|
Versiunea curentă din 4 iunie 2024 08:49
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()