[Python] ABC159D (Mathématiques au lycée nCr) [At Coder]

Les pros de la compétition prépareront un cahier et un stylo! !! !! (Surtout quand une formule mathématique sort)

ABC159D Difficulty:417 Cette fois, je vais expliquer l'explication w Premièrement, cité de Explication.

① Nombre de méthodes pour sélectionner deux boules différentes avec le même entier écrit parmi N boules (2) Nombre de méthodes pour sélectionner une balle avec le même entier que la kème balle à partir de N-1 balles à l'exclusion de la kème balle Peut être obtenu en soustrayant ce dernier du premier. Le premier est ∑Ni = 1 (ci 2) et le second est cAk-1.

** Ce dernier est "cAk-1". ** ** Pourquoi!

Ce dernier est "cAk-1". Sens de

Dans un tel cas, pensez à un exemple concret et trouvez la règle (c'est impossible sans cahier et stylo!)
Exemple spécifique 1
Choisissez 2 sur 5 → 5C2 = 5 * 4/2 * 1 = 10 façons! Choisissez 2 sur 4 → 4C2 = 4 * 3/2 * 1 = 6 façons! ⇨ 10-6 = 4 façons de réduire! Certes, cAk − 1 = 5-1 = 4 voies ont diminué.
Exemple spécifique 2
Choisissez 2 sur 6 → 6C2 = 6 * 5/2 * 1 = 15 façons! Choisissez 2 sur 5 → 5C2 = 5 * 4/2 * 1 = 10 façons! ⇨ 15-10 = 5 façons de réduire! Certainement cAk − 1 = 6-1 = 5 voies ont diminué!
Exemple spécifique 3
Choisissez 2 sur 7 → 7C2 = 7 * 6/2 * 1 = 21 façons! Choisissez 2 sur 6 → 6C2 = 6 * 5/2 * 1 = 15 façons! ⇨ 21-15 = 6 façons de réduire! Certes, cAk − 1 = 7-1 = 6 voies ont diminué! !! !!

Afin d'obtenir AC rapidement pendant la compétition, je pense qu'il est normal de commencer à mettre en œuvre le programme dès que les règles se transforment en condamnation. Je m'inquiète pour n, alors je vais essayer ...

Exemple spécifique n
Sélectionnez 2 sur n → nC2 = n * (n-1) / 2 * 1 Sélectionnez 2 sur n-1 → (n-1) C2 = (n-1) * (n-2) / 2 * 1 n*(n-1)/2　- (n-1)*(n-2)/2 =( (n^2-n) - (n^2-3n+2) )/2 =(2n-2)/2

=「n-1」

Je vois··· Les cahiers et les stylos sont importants! !! !!

Réponse réelle

test.py

import collections
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
A = LI()
count = collections.Counter(A) #Ce mec est comme un dictionnaire
sum = 0
for x in count.values():
    sum += x*(x-1)//2
for x in A:
    print(sum-(count[x]-1))

La quantité de source était étonnamment petite ...

Une autre solution

test.py

import collections
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
A = LI()
count = collections.Counter(A)
sum = 0
for x in count.values():
    sum += x*(x-1)//2
for x in A:
    temp = count[x]
    minus = temp*(temp-1)//2
    plus = (temp-1)*(temp-2)//2
    print(sum-minus+plus)

Il est interdit d'utiliser le sol facilement!

Personne n'a essayé de calculer le nC2 en utilisant un plancher. ~~ Je suis ~~ Le sol math.factorial () ne supporte pas les nombres énormes (limite supérieure 2 * 10 ^ 5 cette fois)! !! !! TLE sera viré! !! !! ~~ J'ai utilisé math.factorial () pour arracher de force l'AC avec PyPy. ~~

python

#Absolument pas.
math.factorial(x)//((math.factorial(x-2))*(math.factorial(2)))

fin!