[Python] ABC159D (High School Mathematics nCr) [Bei Coder]

Leistungsprofis bereiten ein Notizbuch und einen Stift vor! !! !! (Besonders wenn eine mathematische Formel herauskommt)

ABC159D Difficulty:417 Dieses Mal werde ich die Erklärung w erklären Zunächst zitiert aus Erklärung.

① Anzahl der Methoden zur Auswahl von zwei verschiedenen Bällen mit derselben geschriebenen Ganzzahl aus N Bällen (2) Anzahl der Methoden zur Auswahl eines Balls mit derselben ganzen Zahl wie der k-te Ball aus N-1-Bällen ohne den k-ten Ball Kann durch Subtrahieren des letzteren vom ersteren erhalten werden. Ersteres ist ∑Ni = 1 (ci 2) und letzteres ist cAk-1.

** Letzteres ist "cAk-1". ** **. Warum!

Letzteres ist "cAk-1". Bedeutung von

Denken Sie in einem solchen Fall an ein konkretes Beispiel und finden Sie die Regel (ohne Notizbuch und Stift ist das nicht möglich!).
Spezifisches Beispiel 1
Wählen Sie 2 von 5 → 5C2 = 5 * 4/2 * 1 = 10 Möglichkeiten! Wählen Sie 2 von 4 → 4C2 = 4 * 3/2 * 1 = 6 Möglichkeiten! ⇨ 10-6 = 4 Möglichkeiten zur Reduzierung! Sicherlich haben cAk - 1 = 5-1 = 4 Wege abgenommen.
Spezifisches Beispiel 2
Wählen Sie 2 von 6 → 6C2 = 6 * 5/2 * 1 = 15 Möglichkeiten! Wählen Sie 2 von 5 → 5C2 = 5 * 4/2 * 1 = 10 Möglichkeiten! ⇨ 15-10 = 5 Möglichkeiten zur Reduzierung! Sicherlich haben cAk - 1 = 6-1 = 5 Wege abgenommen!
Spezifisches Beispiel 3
Wählen Sie 2 von 7 → 7C2 = 7 * 6/2 * 1 = 21 Möglichkeiten! Wählen Sie 2 von 6 → 6C2 = 6 * 5/2 * 1 = 15 Möglichkeiten! ⇨ 21-15 = 6 Möglichkeiten zur Reduzierung! Sicherlich haben cAk - 1 = 7-1 = 6 Wege abgenommen! !! !!

Um während des eigentlichen Wettbewerbs schnell AC zu bekommen, halte ich es für in Ordnung, mit der Implementierung des Programms zu beginnen, sobald sich die Regeln in Überzeugung ändern. Ich mache mir Sorgen um n, also werde ich es versuchen ...

Spezifisches Beispiel n
Wählen Sie 2 aus n → nC2 = n * (n-1) / 2 * 1 Wählen Sie 2 aus 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」

Das war's··· Notizbücher und Stifte sind wichtig! !! !!

Aktuelle Antwort

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) #Dieser Typ ist wie ein Wörterbuch
sum = 0
for x in count.values():
    sum += x*(x-1)//2
for x in A:
    print(sum-(count[x]-1))

Die Menge der Quelle war unerwartet gering ...

Eine andere Lösung

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)

Es ist verboten, den Boden leicht zu benutzen!

Niemand hat versucht, nC2 mit Fußböden zu berechnen. ~~ Ich bin ~~ Der Boden math.factorial () kann die riesigen Zahlen nicht aushalten (Obergrenze 2 * 10 ^ 5 diesmal)! !! !! TLE wird gefeuert! !! !! ~~ Ich habe math.factorial () verwendet, um PyPy zu zwingen, die Klimaanlage abzureißen. ~~

python

#Definitiv nein.
math.factorial(x)//((math.factorial(x-2))*(math.factorial(2)))

Ende!